首页 > 代码库 > 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 }
BZOJ3289 Mato的文件管理
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。