HDU4184 shallot

【题目描述】

小苗去市场上买了一捆小葱苗，她突然一时兴起，于是她在每颗小葱苗上写上一个数字，然后把小葱叫过来玩游戏。

每个时刻她会给小葱一颗小葱苗或者是从小葱手里拿走一颗小葱苗，并且让小葱从自己手中的小葱苗里选出一些小葱苗使得选出的小葱苗上的数字的异或和最大。

这种小问题对于小葱来说当然不在话下，但是他的身边没有电脑，于是他打电话给同为Oi选手的你，你能帮帮他吗？

你只需要输出最大的异或和即可，若小葱手中没有小葱苗则输出 $0$ 。

【输入】

第一行一个正整数 $n$ 表示总时间；第二行 $n$ 个整数 $a_{1}, a_{2} . . . a_{n}$ ，若 $a_{i}$ 大于 $0$ 代表给了小葱一颗数字为 $a_{i}$ 的小葱苗，否则代表从小葱手中拿走一颗数字为 $- a_{i}$ 的小葱苗。

【输出】

输出共n行，每行一个整数代表第i个时刻的最大异或和。

【输入样例】

6
1 2 3 4 -2 -3

【输出样例】

【提示】

$N \leq 500000, A_{i} \leq 2^{31} - 1$ 。

学到新操(tao)作(lu)——线段树分治。

考虑对整个时间轴建立线段树。由于每一个数出现多次和出现一次是等价的，我们处理出每一个数出现的时间区间（这一步像我一样懒得化可以用map，233），把每一个区间分为log个线段树内的区间节点（每一个节点下挂一个vector，相当于区间修改操作，类似标记永久化）。这样做之后我们计算答案就只需要遍历线段树，把当前的线性基传给下一层就行了。

#include<cstdio>
#include<cstring>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;
const int stmax = 1 << 30;
const int maxn = 5e5 + 5;
typedef pair<int, int > pii;
int ans[maxn];
pii tmp;

struct LNB {
    int LB[35];
    void init() {memset(LB, 0, sizeof(LB));}
    void insert(int u) {
        for(register int i = stmax, p = 30; i > 0; i >>= 1, --p) {
            if(!(u & i)) continue;
            if(!LB[p]) {LB[p] = u; break;}
            else u ^= LB[p];
        }
    }
    int qmax(int x) {
        for(register int i = 30; i >= 0; --i)
            if((x ^ LB[i]) > x) x ^= LB[i];
        return x;
    }
};

map<int, pii > mp;
map<int, pii >::iterator its;
namespace SGT {
	struct node {
		vector<int > nums;
	}tree[maxn << 2];
	void add(int l, int r, int tl, int tr, int num, int rt) {
		if(tl == l && tr == r) 
			return tree[rt].nums.push_back(num), void();
		int mid = tl + tr >> 1;
		if(r <= mid) add(l, r, tl, mid, num, rt << 1);
		else if(l > mid) add(l, r, mid + 1, tr, num, rt << 1 | 1);
		else {
			add(l, mid, tl, mid, num, rt << 1);
			add(mid + 1, r, mid + 1, tr, num, rt << 1 | 1);
		}
	}
	void Gans(int l, int r, int rt, LNB now) {
		for(register int i = tree[rt].nums.size() - 1; i >= 0; --i)
			now.insert(tree[rt].nums[i]);
		if(l == r) return ans[l] = now.qmax(0), void();
		int mid = l + r >> 1;
		Gans(l, mid, rt << 1, now);
		Gans(mid + 1, r, rt << 1 | 1, now);
	}
}

LNB now;
int a[maxn], n, L[maxn], R[maxn], num[maxn], cnt;
int main() {
	scanf("%d", &n), now.init();
	for(register int i = 1; i <= n; ++i)
		scanf("%d", &a[i]);
	for(register int i = 1; i <= n; ++i) {
		if(a[i] > 0) {
			tmp = mp[a[i]];
			if(!tmp.first) mp[a[i]] = make_pair(i, 1);
			else ++mp[a[i]].second;
		} else {
			tmp = mp[-a[i]];
			if(tmp.second == 1) {
				L[++cnt] = tmp.first, R[cnt] = i - 1, num[cnt] = -a[i];
				mp.erase(-a[i]);
			} else --mp[-a[i]].second;
		}
	}
	for(its = mp.begin(); its != mp.end(); ++its) {
		L[++cnt] = its -> second . first;
		R[cnt] = n, num[cnt] = its -> first;
	}
	for(register int i = 1; i <= cnt; ++i)
		SGT::add(L[i], R[i], 1, n, num[i], 1);
	SGT::Gans(1, n, 1, now);
	for(register int i = 1; i <= n; ++i)
		printf("%d\n", ans[i]);
	return 0;
}

Rockdu's Blog