首页 > 代码库 > BZOJ3744 Gty的妹子序列
BZOJ3744 Gty的妹子序列
我kao终于搞定了。。。
总之妹子序列比妹子树好些。。。妹子树至今还不会。。。
这题就是强制在线的区间逆序对个数。。。
神马主席树的太高端了。。。早忘了。。。额T T（怪我咯？><）
首先我们分块，求出连续块内的答案，方法是直接用BIT暴力求。。。
复杂度为O(n ^ 2 / size * log(n ^ 2 / size))（size为一块的大小）
然后回答的时候，中间整段的都有了，只要看两边多出来的就可以了，方法是直接用BIT暴力求。。。额。。。
查询一次的最坏复杂度为O(2size * log(size))（size为一块的大小）
总之就是暴力求。。。
接着我们来看一下了啦~~~size去什么值比较好呢？
n ^ 2 / size * log(n ^ 2 / size) + m * size * log(size)最小。。
神马展开的。。。然后求导。。。我去。。。
那些数学高联1=的人。。。你倒是给我算出来啊！
还是乖乖地取size = sqrt(n)算了。。。
1 /************************************************************** 2 Problem: 3744 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:10876 ms 7 Memory:50872 kb 8 ****************************************************************/ 9 10 #include <cstdio> 11 #include <cmath> 12 #include <cctype> 13 #include <cstring> 14 #include <algorithm> 15 16 #define lowbit(x) x & -x 17 using namespace std; 18 19 const int N = 50005; 20 const int B = 250; 21 int n, m; 22 int T, block, size; 23 int pos[N], st[B]; 24 int BIT[N], vis[N]; 25 int ans[B][B]; 26 int cnt[B][N]; 27 int a[N], b[N]; 28 29 inline int read() { 30 int x = 0; 31 char ch = getchar(); 32 while (!isdigit(ch)) 33 ch = getchar(); 34 while (isdigit(ch)) { 35 x = x * 10 + ch - ‘0‘; 36 ch = getchar(); 37 } 38 return x; 39 } 40 41 inline int find(const int x) { 42 int l = 1, r = n + 1, mid; 43 while (l + 1 < r) { 44 mid = (l + r) >> 1; 45 if (b[mid] <= x) l = mid; 46 else r = mid; 47 } 48 return l; 49 } 50 51 inline void add(int x){ 52 while (x <= n) { 53 if (vis[x] != T) vis[x] = T, BIT[x] = 1; 54 else ++BIT[x]; 55 x += lowbit(x); 56 } 57 } 58 59 inline int query(int x) { 60 int res = 0; 61 while(x) { 62 if (vis[x] == T) 63 res += BIT[x]; 64 x -= lowbit(x); 65 } 66 return res; 67 } 68 69 int Work(int l, int r) { 70 ++T; 71 if (pos[l] == pos[r]) { 72 int res = 0; 73 for (; r >= l; --r) 74 res += query(a[r] - 1), add(a[r]); 75 return res; 76 } 77 int res, cnt_all, i; 78 res = ans[pos[l] + 1][pos[r] - 1]; 79 cnt_all = st[pos[r]] - st[pos[l] + 1]; 80 for (i = st[pos[l] + 1] - 1; i >= l; --i) { 81 res += query(a[i] - 1) + cnt[pos[r] - 1][a[i] - 1] - cnt[pos[l]][a[i] - 1]; 82 add(a[i]), ++cnt_all; 83 } 84 for (i = st[pos[r]]; i <= r; ++i) { 85 res += cnt_all - query(a[i]) - cnt[pos[r] - 1][a[i]] + cnt[pos[l]][a[i]]; 86 add(a[i]), ++cnt_all; 87 } 88 return res; 89 } 90 91 void Block() { 92 int i; 93 size = (int) sqrt(n); 94 for (i = 1; i <= n; ++i) 95 pos[i] = (i - 1) / size + 1; 96 block = pos[n]; 97 for (i = 1; i <= block; ++i) 98 st[i] = size * (i - 1) + 1; 99 st[block + 1] = n + 1;100 }101 102 void pre_work() {103 int cnt_now, cnt_all, i, j, k;104 for (i = 1; i <= block; ++i) {105 cnt_now = cnt_all = 0, ++T;106 memcpy(cnt[i], cnt[i - 1], sizeof(cnt[i]));107 for (j = i; j <= block; ++j)108 for (k = st[j]; k <= st[j + 1] - 1; ++k) {109 cnt_now += cnt_all - query(a[k]);110 ans[i][j] = cnt_now;111 add(a[k]);112 ++cnt_all, ++cnt[j][a[k]];113 }114 }115 for (i = 1; i <= block; ++i)116 for (j = 2; j <= n; ++j)117 cnt[i][j] += cnt[i][j - 1];118 }119 120 int main() {121 int i;122 n = read();123 for (i = 1; i <= n; ++i)124 a[i] = b[i] = read();125 m = read();126 sort(b + 1, b + n + 1);127 for (i = 1; i <= n; ++i)128 a[i] = find(a[i]);129 Block();130 pre_work();131 int L, R, ans = 0;132 while (m--) {133 L = read() ^ ans, R = read() ^ ans;134 printf("%d\n", ans = Work(L, R));135 }136 return 0;137 }
（p.s. Rank10貌似还可以的样子。。。话说小号为了调参连T5次。。。估计是快要被权限掉了Orz）
BZOJ3744 Gty的妹子序列
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。