CF 220E, 树状数组

维护逆序对的树状数组瓜题，就不报告了（手抖强行wa两发）
  1 #include <cstdio>
  2 #include <string>
  3 #include <iostream>
  4 #include <algorithm>
  5 #include <cmath>
  6 #include <cstring>
  7 #include <complex>
  8 #include <set>
  9 #include <vector>
 10 #include <map>
 11 #include <queue>
 12 #include <deque>
 13 #include <ctime>
 14 
 15 using namespace std;
 16 
 17 const double EPS = 1e-8;
 18 
 19 #define ABS(x) ((x)<0?(-(x)):(x))
 20 #define SQR(x) ((x)*(x))
 21 #define MIN(a,b) ((a)<(b)?(a):(b))
 22 #define MAX(a,b) ((a)>(b)?(a):(b))
 23 
 24 #define LSON(x) ((x)<<1)
 25 #define RSON(x) (((x)<<1)+1)
 26 #define LOWBIT(x) ((x)&(-(x)))
 27 #define MAXS 1111
 28 #define MAXN 222222
 29 #define VOIDPOINT 0
 30 #define LL long long
 31 #define OO 214748364
 32 
 33 struct TreeArray{
 34     int tree[MAXN], n;
 35     int f[MAXN];
 36     void clear(int nn = MAXN - 20) {
 37         n = nn;
 38         memset(tree, 0, sizeof(tree[0])*(n+10));
 39         memset(f, 0, sizeof(f[0])*(n+10));
 40     }
 41     void add(int x, int num = 1) {
 42         if (x < 1) puts("Error in TreeArray, x must > 0!!");
 43         f[x] += num;
 44         while (x <= n) {
 45             tree[x] += num;
 46             x += LOWBIT(x);
 47         }
 48     }
 49     int get(int x) {
 50         int res = 0;
 51         while (x > 0) {
 52             res += tree[x];
 53             x -= LOWBIT(x);
 54         }
 55         return res;
 56     }
 57     int getright(int x) { // get [x ~ n]
 58         return get(n) - get(x-1);
 59     }
 60     int take(int x, int k) { //树状数组二分前面第k个1的位置尝试，类似区间查询
 61         int res = 0, sum = 0;
 62         sum = get(x);
 63         while (sum) {
 64             if (sum == k && f[x]) {
 65                 res = x; break;
 66             }
 67             if (sum - tree[x] >= k) {
 68                 sum -= tree[x];
 69                 x -= LOWBIT(x);
 70             } else {
 71                 if (f[x]) sum -= f[x];
 72                 --x;
 73             }
 74         }
 75         add(res, -1);
 76         return res;
 77     }
 78 } TreeL, TreeR;
 79 
 80 int a[MAXN];
 81 vector <int > lsh;
 82 LL ans, n, k;
 83 
 84 void init() {
 85     lsh.clear();
 86     for (int i = 0; i < n; ++i) {
 87         scanf("%d", a+i);
 88         lsh.push_back(a[i]);
 89     }
 90     sort(lsh.begin(), lsh.end());
 91     lsh.erase(unique(lsh.begin(), lsh.end()), lsh.end());
 92     for (int i = 0; i < n; ++i) a[i] = lower_bound(lsh.begin(), lsh.end(), a[i]) - lsh.begin() + 1;
 93 }
 94 
 95 void solve() {
 96     ans = 0;
 97     int sum = 0, head = 0, tail = n;
 98     TreeL.clear(n); TreeR.clear(n);
 99     TreeL.add(a[0]); 
100     while (head + 1 < tail && 
101     sum + TreeL.getright(a[tail-1]+1) + TreeR.get(a[tail-1]-1) <= k) {
102         sum += TreeL.getright(a[tail-1]+1) + TreeR.get(a[tail-1]-1);
103         --tail;
104         TreeR.add(a[tail]);
105     }
106 
107     ans += n - tail;
108 
109 
110     for (head = 1; head < n; ++head) {
111         if (head == tail) {
112             sum -= (TreeL.getright(a[tail]+1) + TreeR.get(a[tail]-1));
113             TreeR.add(a[tail++], -1);
114         }
115         TreeL.add(a[head]);
116         sum += TreeL.getright(a[head]+1) + TreeR.get(a[head]-1); 
117         while (sum > k && tail < n) {
118             sum -= TreeL.getright(a[tail]+1) + TreeR.get(a[tail]-1);
119             TreeR.add(a[tail++], -1);
120         }
121         ans += n - tail;
122     }
123 }
124 
125 int main() {
126 //    freopen("test.txt", "r", stdin);
127     while (cin >> n >> k) {
128         init();
129         solve();
130         cout << ans << endl;
131     }
132     return 0;
133 }
CF 220E