Rockdu's Blog
“Where there is will, there is a way”
亲 您的浏览器不支持html5的audio标签
Toggle navigation
Rockdu's Blog
主页
数据结构
字符串算法
图论
数论、数学
动态规划
基础算法
[其它内容]
计算几何
科研笔记
归档
标签
LOJ#517. 「LibreOJ β Round #2」计算几何瞎暴力
? 解题记录 ?
? LOJ ?
? 字典树 ?
2019-03-14 15:26:58
569
0
0
rockdu
? 解题记录 ?
? LOJ ?
? 字典树 ?
[题目链接](https://loj.ac/problem/517) 题解:发现只需要分两段维护就可以了。 上一次排过序的前缀部分用字典树维护,并且对每一位记录$now_xor$表示按照当前的顺序,第$i$位是否被翻转。后面的部分用一个前缀和维护。 这样的话,异或的时候维护偏移值,每一次排序我们就把后面的部分全部插入字典树,并且更新$now\_xor$。 ``` #include<cstdio> #include<algorithm> #include<cstring> #define LL long long using namespace std; const int maxn = 2e5 + 5; namespace Trie { int trie[maxn * 30][2], sz[maxn * 30], cnt, root; int bits_1[maxn * 30][30], now_xor[30], out_xor[30], oxor; void push_up(int rt) { sz[rt] = sz[trie[rt][0]] + sz[trie[rt][1]]; int tl = trie[rt][0], tr = trie[rt][1]; for(register int i = 0; i < 30; ++i) { bits_1[rt][i] = bits_1[tl][i] + bits_1[tr][i]; } } void insert(int x, int b, int &rt) { if(!rt) rt = ++cnt; if(b == -1) { ++sz[rt]; for(register int i = 0; i < 30; ++i) if(((1 << i) & x)) ++bits_1[rt][i]; return ; } insert(x, b - 1, trie[rt][(bool) ((1 << b) & x)]); push_up(rt); } void query(int p, int rt, int b, int ans[30]) { if(b == -1) { if(p) { for(register int i = 0; i < 30; ++i) if(bits_1[rt][i]) ans[i] += p; } return ; } int tl = trie[rt][now_xor[b]], tr = trie[rt][now_xor[b] ^ 1]; if(sz[tl] >= p) query(p, tl, b - 1, ans); else { for(register int i = 0; i < 30; ++i) ans[i] += bits_1[tl][i]; query(p - sz[tl], tr, b - 1, ans); } } int tmp1[30], tmp2[30]; void Ins(int x) { insert(x, 29, root); } LL Q(int l, int r) { LL ans = 0; memset(tmp2, 0, sizeof(tmp2)); memset(tmp1, 0, sizeof(tmp1)); query(l - 1, 1, 29, tmp1); for(register int i = 0; i < 30; ++i) if(out_xor[i]) tmp1[i] = l - 1 - tmp1[i]; query(r, 1, 29, tmp2); for(register int i = 0; i < 30; ++i) if(out_xor[i]) tmp2[i] = r - tmp2[i]; for(register int i = 0; i < 30; ++i) { ans += 1ll * (1 << i) * (tmp2[i] - tmp1[i]); //else ans += 1ll * (1 << i) * (r - l + 1 - (tmp2[i] - tmp1[i])); } return ans; } } int ob[maxn][30], num[maxn], ncnt, pos; void Ins(int x) { using namespace Trie; num[++ncnt] = x ^ oxor; for(register int i = 0; i < 30; ++i) ob[ncnt][i] = (((bool)(x & (1 << i))) ^ out_xor[i]) + ob[ncnt - 1][i]; } void Sort() { using namespace Trie; for(register int i = 0; i < 30; ++i) now_xor[i] = out_xor[i]; pos += ncnt; for(register int i = 1; i <= ncnt; ++i) Trie::Ins(num[i]); ncnt = 0; } LL query(int l, int r) { using namespace Trie; LL ans = 0; for(register int i = 0; i < 30; ++i) { if(!out_xor[i]) ans += 1ll * (1 << i) * (ob[r][i] - ob[l - 1][i]); else ans += 1ll * (1 << i) * (r - l + 1 - (ob[r][i] - ob[l - 1][i])); } return ans; } void All_Xor(int x) { using namespace Trie; oxor ^= x; for(register int i = 0; i < 30; ++i) { out_xor[i] ^= (bool) (x & (1 << i)); } } LL Q(int l, int r) { if(r <= pos) return Trie::Q(l, r); else if(l > pos) return query(l - pos, r - pos); else return Trie::Q(l, pos) + query(1, r - pos); } int main() { int n, m, op, a, b; scanf("%d", &n); for(register int i = 1; i <= n; ++i) scanf("%d", &a), Ins(a); scanf("%d", &m); for(register int i = 1; i <= m; ++i) { scanf("%d", &op); if(op == 1) scanf("%d", &a), Ins(a); else if(op == 2) scanf("%d%d", &a, &b), printf("%lld\n", Q(a, b)); else if(op == 3) scanf("%d", &a), All_Xor(a); else Sort(); } return 0; } ```
上一篇:
HDU5599 GTW likes tree
下一篇:
LOJ#6289. 花朵
0
赞
569 人读过
新浪微博
微信
腾讯微博
QQ空间
人人网
提交评论
立即登录
, 发表评论.
没有帐号?
立即注册
0
条评论
More...
文档导航
没有帐号? 立即注册