本文共 2886 字，大约阅读时间需要 9 分钟。
题意：给出n； n个人有n个不同的技能值 问 任取三个人 使得 中间那人的 技能值也在其他两人之间。
树状数组
#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;typedef long long LL;const LL maxn = 100000 + 100;LL Max;LL c[maxn];LL zuomin[maxn],youmin[maxn],zuomax[maxn],youmax[maxn];LL lowbit(LL x){ return x&(-x);}void update(LL x, LL add){ while (x <= Max){ c[x] += add; x += lowbit(x); }}LL ask(LL x){ LL ans = 0; while (x > 0){ ans += c[x]; x -= lowbit(x); } return ans;}int main(){ LL n; LL a[maxn],Icase; cin>>Icase; while (Icase--){ cin>>n; Max = -1; for (LL i = 1; i <= n; i++) cin >> a[i],Max = max(Max,a[i]); memset(c, 0, sizeof(c)); for (LL i = 1; i <= n; i++){ zuomin[i] = ask(a[i]); zuomax[i]= ask(Max) - ask(a[i]); update(a[i], 1);//边统计左边比他大和比他小的 ，边插 } memset(c, 0, sizeof(c)); for (LL i = n; i >= 1; i--){ youmin[i] = ask(a[i]); youmax[i] = ask(Max) - ask(a[i]); update(a[i], 1); } LL ans = 0; for (LL i = 1; i <= n; i++){ ans += zuomin[i] * youmax[i]; ans += zuomax[i] * youmin[i]; } cout << ans << endl; } return 0;}
线段树
#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;typedef long long LL;const int maxn = 100000 + 100;#define lson l,mid,rt<<1#define rson mid+1,r,rt<<1|1int sum[maxn * 4];int zuomin[maxn], youmin[maxn], zuomax[maxn], youmax[maxn];void up(int rt){ sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];}void build(int l, int r, int rt){ sum[rt] = 0; if (l == r) return; int mid = (l + r) >> 1; build(lson); build(rson);}void update(int pos, int add, int l, int r, int rt){ if (l == r){ sum[rt] = 1; return; } int mid = (l + r) >> 1; if (pos <= mid) update(pos, add, lson); else update(pos, add, rson); up(rt);}int ask(int L, int R, int l, int r, int rt){ if (L <= l&&r <= R) return sum[rt]; int mid = (l + r) >> 1; int ans = 0; if (L <= mid) ans += ask(L, R, lson); if (R > mid) ans += ask(L, R, rson); return ans;}int main(){ int Icase; int n, Max; int a[maxn]; cin >> Icase; while (Icase--){ cin >> n; Max = -1; for (int i = 1; i <= n; i++) scanf("%d", &a[i]), Max = max(Max, a[i]); build(1, Max, 1); for (int i = 1; i <= n; i++){ zuomin[i] = ask(1,a[i],1,Max,1); zuomax[i] = ask(1,Max,1,Max,1) - ask(1,a[i],1,Max,1); update(a[i], 1,1,Max,1); } build(1, Max, 1); for (int i = n; i >= 1; i--){ youmin[i] = ask(1,a[i],1,Max,1); youmax[i] = ask(1,Max,1,Max,1) - ask(1,a[i],1,Max,1); update(a[i], 1,1,Max,1); } LL ans = 0; for (int i = 1; i <= n; i++){ ans += zuomin[i] * youmax[i]; ans += zuomax[i] * youmin[i]; } cout << ans << endl; } return 0;}
转载于:https://www.cnblogs.com/yigexigua/p/4018428.html