BZOJ 3217: ALOEXT (块状链表套trie)

第一次写块状链表,发现还挺好写的,但是一点地方写错加上强制在线就会各种姿势WA/TLE/RE爆…

想法就是分块后,在每一个块上维护最大值和次大值,还在每一个块上维护一棵trie树来求异或最大值.散块直接暴力…这想法暴力吧…这道题不用考虑合并,因为最多分出(n+q)/Bsz块.详细的做法如下

对于修改一个数，首先在该块的trie数中删除该数（直接伪删,也就是让那一条路径上每个点的cnt都减1），然后再插入，接着更新最大值和次大值。

对于插入一个数，直接在trie树中插入该数，随后在块状链表中插入，更新最大值和次大值。最后判断是否要将该块拆分（如果要拆分直接暴力重构两个块即可）

对于删除一个数，trie树伪删除+块链删除+更新最大值和次大值。随后判断该块大小是否等于0（为零可以直接删掉这个块了）

对于查询最大值，首先查询出该区间内的次大值。对于完全包含的块，直接将该值丢到该块的trie树中求最大值，对于非完全包含的块，直接暴力求即可。

摘自博客AlphaINF(表示吐槽代码中统计答案的时候写的四个if语句,直接取个max,取个min不就行了吗…)

设块的大小为$B$B,且设$n,q$n,q同阶.总时间复杂度为$O(n*B+n*n/B*20)$O(n∗B+n∗n/B∗20),这里的$20$20是在trie树上求最大值的时间复杂度.那么最小时间复杂度就是$B=n/B*20$B=n/B∗20,即$B=sqrt{20n}$B=20n​,约是$2000$2000.但由于我不考虑合并,那么还可以开大一点.最后我开了$2500$2500

然后就$BZOJ$BZOJ第一页了…

#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;
char cb[1<<15],*cs=cb,*ct=cb;
#define getc() (cs==ct&&(ct=(cs=cb)+fread(cb,1,1<<15,stdin),cs==ct)?0:*cs++)
template<class T>inline void read(T &res) {
    char ch; for(;!isdigit(ch=getc()););
    for(res=ch-'0';isdigit(ch=getc());res=res*10+ch-'0');
}
typedef long long LL;
const int Bsz = 2500;
const int M = 5000005;
const int LOG = 20;
int n, q;
struct node {
	int mx1, mx2;
	node(){ mx1 = mx2 = 0; }
	node(int m1, int m2):mx1(m1), mx2(m2) {}
	inline void operator +=(const node &o) {
		if(o.mx1 > mx1) mx2 = mx1, mx1 = o.mx1;
		else if(o.mx1 > mx2) mx2 = o.mx1;
		if(o.mx2 > mx2) mx2 = o.mx2;
	}
};
struct Block {
	int a[Bsz+1], use, nxt, rt;
	node val;
	Block() {
		memset(a, 0, sizeof a);
		use = nxt = rt = val.mx1 = val.mx2 = 0;
	}
	inline void getmax() {
		val = node(0, 0);
		for(int i = 1; i <= use; ++i)
			val += node(a[i], 0);
	}
}b[100];
int ch[M][2], cnt[M], tot;
inline void add(int &rt, int x, int val) {
	if(!rt) rt = ++tot;
	int r = rt;
	for(int bit = 1<<(LOG-1); bit; bit>>=1) {
		bool i = (x&bit); cnt[r] += val;
		if(!ch[r][i]) ch[r][i] = ++tot;
		r = ch[r][i];
	}
	cnt[r] += val;
}
inline int Getmax(int rt, int x) {
	int r = rt, res = 0;
	for(int bit = 1<<(LOG-1); bit; bit>>=1) {
		bool i = !(x&bit);
		if(cnt[ch[r][i]]) res += bit;
		else i ^= 1;
		r = ch[r][i];
	}
	return res;
}

int blocks = 1;
inline void modify(int pos, int val) {
    int i, last;
    for(i = 1; i; i = b[i].nxt)
        if(b[i].use >= pos) {
            last = b[i].a[pos], b[i].a[pos] = val;
            add(b[i].rt, last, -1);
            add(b[i].rt, val, 1);
            b[i].getmax();
            return; //这里忘了return...
        }
        else pos -= b[i].use;
}
inline void cut(int i) {
    int j = ++blocks;
    b[i].use = b[j].use = Bsz/2;
    b[j].nxt = b[i].nxt, b[i].nxt = j;
    b[i].rt = 0; b[j].rt = 0;
    for(int k = 1; k <= Bsz/2; ++k) {
        b[j].a[k] = b[i].a[k+Bsz/2], b[i].a[k+Bsz/2] = 0;
        add(b[i].rt, b[i].a[k], 1);
        add(b[j].rt, b[j].a[k], 1);
    }
    b[i].getmax(), b[j].getmax();
}
 
inline void insert(int pos, int x) {
    int i, pre;
    for(i = 1; i; pre = i, i = b[i].nxt)
        if(b[i].use < pos) pos -= b[i].use;
        else break;
    if(!i) i = pre, pos += b[i].use;
    for(int j = b[i].use; j >= pos; --j)
        b[i].a[j+1] = b[i].a[j];
    b[i].a[pos] = x, ++b[i].use;
    add(b[i].rt, x, 1);
    b[i].val += node(x, 0);
    if(b[i].use >= Bsz) cut(i);
}
inline void del(int pos) {
    int i, pre = 1, x;
    for(i = 1; i; pre = i, i = b[i].nxt)
        if(b[i].use >= pos) {
            x = b[i].a[pos]; add(b[i].rt, x, -1);
            for(int j = pos; j <= b[i].use; ++j)
                b[i].a[j] = b[i].a[j+1];
            if(--b[i].use == 0) { b[pre].nxt = b[i].nxt; return; }
            if(x >= b[i].val.mx2) b[i].getmax();
			return;
        }
        else pos -= b[i].use;
}
inline int getmax2(int L, int R) {
    int i, bot = 0, l, r; node res;
    for(i = 1; i; bot += b[i].use, i = b[i].nxt) {
        l = L - bot, r = R - bot;
        if(l < 1 && r < 1) break;
        if(l > b[i].use && r > b[i].use) continue;
        l = max(l, 1), r = min(b[i].use, r);
        if(l == 1 && r == b[i].use) res += b[i].val;
        else for(int j = l; j <= r; ++j) res += node(b[i].a[j], 0);
    }
    return res.mx2;
}
 
inline int query(int L, int R) {
    int i, tmp = getmax2(L, R), bot = 0, res = 0, l, r;
    for(i = 1; i; bot += b[i].use, i = b[i].nxt) {
        l = L - bot, r = R - bot;
        if(l < 1 && r < 1) break;
        if(l > b[i].use && r > b[i].use) continue;
        l = max(l, 1), r = min(b[i].use, r);
        if(l == 1 && r == b[i].use) res = max(res, Getmax(b[i].rt, tmp));
        else for(int j = l; j <= r; ++j) res = max(res, tmp^b[i].a[j]);
    }
    return res;
}

int main () {
	read(n), read(q);
	for(int i = 1, x; i <= n; ++i)
		read(x), insert(i, x);
	char s[2]; int x, y, lastans = 0;
	while(q--) {
		while(!isalpha(s[0]=getc()));
		read(x), x = (x + lastans) % n + 1;
		if(s[0] == 'D') { del(x), --n; continue; }
		read(y);
		if(s[0] == 'F') y = (y + lastans) % n + 1;
		else y = (y + lastans) % 1048576;
		if(s[0] == 'I') insert(x, y), ++n;
		else if(s[0] == 'C') modify(x, y);
		else printf("%d
", lastans = query(min(x, y), max(x, y)));
	}
	return 0;
}