首页 > 代码库 > BZOJ3289 Mato的文件管理

BZOJ3289 Mato的文件管理

好烦的题,做了我2h,看来蒟蒻就是弱啊。。。

感觉就是莫队算法来着,然后就走上了乱搞的不归路、、、

莫队算法详情请上百度搜索,谢谢!>.<

这道题要求逆序对,所以可以用树状数组动态维护。每次转移复杂度就是树状数组点修改的复杂度,但是转移的时候好烦。。。(一定是我太弱了)

再加上分块,总复杂度为O(n * sqrt(n) * log(n)),刚刚好卡过去。。。

 

  1 /**************************************************************  2     Problem: 3289  3     User: rausen  4     Language: C++  5     Result: Accepted  6     Time:8772 ms  7     Memory:10200 kb  8 ****************************************************************/  9   10 #include <cstdio> 11 #include <cmath> 12 #include <algorithm> 13   14 using namespace std; 15 typedef long long LL; 16   17 struct data{ 18     int l, r, wl, w; 19     LL ans; 20 } a[150000]; 21 inline bool cmp(data a, data b){ 22     return a.wl == b.wl ? a.r < b.r : a.l < b.l; 23 } 24   25 inline bool cmp_id(data a, data b){ 26     return a.w < b.w; 27 } 28   29 LL x[150000], y[150000]; 30 LL BIT[150000], rank[150000]; 31 int TOT, T, tot, w[150000], block[150000]; 32 int n, Q, l, r, num; 33 LL sum; 34   35 void build(){    36     T = (int) sqrt(n), tot = 0; 37     int x = 0; 38     while (x < n) 39         x += T, w[++tot] = x; 40     w[tot] = min(w[tot], n); 41     int y = 1; 42     for (int i = 1; i <= n; ++i) 43         if (i <= w[y]) block[i] = y; 44         else block[i] = ++y; 45 } 46   47 inline int lowbit(int x){ 48     return x & (-x); 49 } 50   51 LL query(int x){ 52     if (x < 0) return 0; 53     LL res = 0; 54     while (x) 55         res += BIT[x], x -= lowbit(x); 56     return res; 57 } 58   59 void change(int x, int del){ 60     while (x <= n) 61         BIT[x] += del, x += lowbit(x); 62 } 63   64 void update_right(int p, int del){ 65     sum += (LL) del * (num - query(x[p])), num += del; 66     change(x[p], del); 67 } 68   69 void update_left(int p, int del){ 70     change(x[p], del);   71     sum += (LL) del * query(x[p] - 1), num += del; 72 } 73   74 int find(int x){ 75     int l = 1, r = TOT, mid; 76     for (; l != r; ){ 77         mid = (l + r) >> 1; 78         if (rank[mid] >= x) r = mid; 79         else l = mid + 1; 80     } 81     return l; 82 } 83   84 int main(){ 85     scanf("%d", &n); 86     for (int i = 1; i <= n; ++i){ 87         scanf("%lld", x + i); 88         y[i] = x[i]; 89     } 90     build(); 91     sort(y + 1, y + n + 1); 92     rank[++TOT] = y[1]; 93     for (int i = 2; i <= n; ++i) 94         if (y[i] != y[i - 1]) 95             rank[++TOT] = y[i]; 96     for (int i = 1; i <= n; ++i) 97         x[i] = find(x[i]); 98       99     scanf("%d", &Q);100     for (int i = 1; i <= Q; ++i){101         scanf("%d%d", &a[i].l, &a[i].r);102         a[i].wl = block[a[i].l], a[i].w = i;103     }104     sort(a + 1, a + Q + 1, cmp);105     l = 1, r = 0, num = sum = 0;106     for (int i = 1; i <= Q; ++i){107         for (; r < a[i].r; ++r) update_right(r + 1, 1);108         for (; r > a[i].r; --r) update_right(r, -1);109         for (; l < a[i].l; ++l) update_left(l, -1);110         for (; l > a[i].l; --l) update_left(l - 1, 1);111         a[i].ans =  a[i].l == a[i].r ? 0 : sum;112     }113      114     sort(a + 1, a + Q + 1, cmp_id);115     for (int i = 1; i <= Q; ++i)116         printf("%lld\n", a[i].ans);117     return 0;118 }
View Code

 

BZOJ3289 Mato的文件管理