给定排列p，求四元组(a, b, c, d)(1 ＜= a ＜ b ＜ c ＜ d ＜= n)的个数，满足p[a] ＜ p[c], p[b] ＞ p[d].

• 编程语言

题目

法一：树状数组

#include 
using namespace std;
// #define int long long
typedef long long ll;
#define pb push_back
#define lson p << 1
#define rson p << 1 | 1
const int maxn = 1e6 + 5, maxm = 5e3 + 5;
int a[maxm];
int n, m;
struct Seg{
	int l, r;
	bool operator  x.r;
	}
};
vector seg, seg2;
int t[maxm];
int lowbit(int x){
	return x & -x;
}
void add(int x, int k){
	for(int i = x; i > n;
	for(int i = 1; i <= n; i++){
		t[i] = 0;
	}
	seg.clear(), seg2.clear();
	for(int i = 1; i > a[i];
	}
	int m = 0, m2 = 0;	
	seg.pb({0, 0}), seg2.pb({0, 0});
	for(int i = 1; i <= n; i++){
		for(int j = i + 1; j <= n; j++){
			if(a[i] < a[j]){
				seg.pb({i, j});
				m++;
			}
			else{
				seg2.pb({i, j});
				m2++;
			}
		}
	}
	sort(seg.begin() + 1, seg.end());
	sort(seg2.begin() + 1, seg2.end());
	int i = 1, j = 1;
	ll res = 0;
	for(int i = 1; i <= m; i++){
		while(j  seg[i].r){
			add(seg2[j].l, 1);
			j++;
		}
		res += ask(seg[i].r - 1) - ask(seg[i].l);
	}
	cout << res <> T;
	// for(int i = 1; i <= T; i++){
	// 	num = i;
	// 	solve();
	// }
	while (T--)
	{
		solve();
	}
}

法二：

#include 
using namespace std;
#define int long long
#define pb push_back
#define lson p << 1
#define rson p <>= 1;
    }
    return res;
}

int __lcm(int a, int b){
    int g = __gcd(a, b);
    return a * b / g;
}

void solve(){
    int res = 0;
    cin >> n;
    for(int i = 1; i <= n; i++){
        f[i] = 0;
    }
    for(int i = 1; i > p[i];
    }
    for(int i = 1; i <= n; i++){
        for(int j = i + 1; j  p[j]){
                f[i]++;
            }
        }
        // cout << i << ' ' << f[i] << '\n';
    }
    for(int c = 3; c <= n; c++){
        for(int b = 1; b  p[c]){
                f[b]--;
            }
        }
        for(int b = 1; b < c; b++){
            pre[b] = pre[b - 1] + f[b];
        }
        for(int a = 1; a <= c - 2; a++){
            if(p[a] < p[c]){
                res += pre[c - 1] - pre[a];
            }
        }
    }
    cout << res << '\n';
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    // fac[0] = 1;
    // for(int i = 1; i > T;
    while (T--)
    {
        solve();
    }
    return 0;
}

本文来自网络，不代表协通编程立场，如若转载，请注明出处：https://net2asp.com/eccab79277.html

赞 (0)
« 上一篇 1天前
下一篇 » 1天前

相关推荐