【BZOJ 4906】[BeiJing2017] 喷式水战改

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4906

解题报告

这题我们看一眼就知道可以用平衡树来维护序列
至于收益问题,我们发现区间信息可以合并
只需要记录一个区间左右两个端点的状态即可
于是搞一个$Splay$然后带$4^3$的常数来合并区间信息即可
总时间复杂度:$O(4^3n \log n)$

Code

这个代码win下没问题
ubuntu 16.04下也没有问题
UOJ的自定义测试也不会RE

然而一交到B站上就RE
我也很绝望啊,弃疗了_(:з」∠)_
反正北京省选测评也是在win下,就当a了吧

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int SGZ = 4;
const int N = 400000;

namespace Splay{
	int tot;
	struct Node *null, *root;
	struct Node{
		Node *ch[2], *fa;
		LL len, plen, adv[SGZ], sum[SGZ][SGZ];
		inline Node() {
		}
		inline Node(LL l, LL a, LL b, LL c) {
			memset(sum, 0, sizeof(sum));
			sum[0][0] = adv[0] = sum[3][3] = adv[3] = l * a;
			sum[1][1] = adv[1] = l * b;
			sum[2][2] = adv[2] = l * c;
			len = plen = l;
			ch[0] = ch[1] = fa = null;
			for (int i = 0; i < SGZ; i++) {
				for (int j = i; j < SGZ; j++) {
					for (int k = i - 1; ~k; k--) {
						sum[k][j] = max(sum[k][j], sum[i][j]);
					}
					for (int k = j + 1; k < SGZ; k++) {
						sum[i][k] = max(sum[i][k], sum[i][j]);
					}
				}
			}
		}
		inline void relax(LL &a, LL b) {
			a = b > a? b: a;
		}
		inline void maintain() {
			memset(sum, 0, sizeof(sum));
			//merge left son
			if (ch[0] != null) {
				for (int i = 0; i < SGZ; i++) {
					for (int k = SGZ - 1; k >= i; k--) {
						for (int j = k; j >= i; j--) {
							relax(sum[i][k], ch[0]->sum[i][j] + adv[k]);
						}
					}
				}
				plen = len + ch[0]->plen;
			} else {
				for (int i = 0; i < SGZ; i++) {
					sum[i][i] = adv[i];
				}
				plen = len;
			}
			//merge right son
			if (ch[1] != null) {
				for (int l = 0; l < SGZ; l++) {
					for (int i = SGZ - 1; i >= l; i--) {
						for (int r = SGZ - 1; r >= i; r--) {
							relax(sum[l][r], sum[l][i] + ch[1]->sum[i][r]);
						}
					}
				}
				plen += ch[1]->plen;
			} 
			for (int i = 0; i < SGZ; i++) {
				for (int j = i; j < SGZ; j++) {
					for (int k = i - 1; ~k; k--) {
						relax(sum[k][j], sum[i][j]);
					}
					for (int k = j + 1; k < SGZ; k++) {
						relax(sum[i][k], sum[i][j]);
					}
				}
			}
		}
		inline void rotate() {
			int t = fa->ch[1] == this;
			if (fa->fa != null) {
				int tt = fa->fa->ch[1] == fa;
				fa->fa->ch[tt] = this;
			}
			fa->ch[t] = ch[t^1]; ch[t^1]->fa = fa;
			ch[t^1] = fa; fa = ch[t^1]->fa;
			ch[t^1]->fa = this;
			ch[t^1]->maintain();
			maintain();
		}
		inline void splay(Node *ed) {
			while (fa != ed) {
				if (fa->fa != ed) {
					if ((fa->ch[0] == this) ^ (fa->fa->ch[0] == fa)) {
						rotate();
						rotate();
					} else {
						fa->rotate();
						rotate();
					}
				} else {
					rotate();
				} 
			}
 		}
 		inline LL ans() {
			LL ret = 0;
			for (int i = 0; i < SGZ; i++) {
				for (int j = i; j < SGZ; j++) {
					ret = max(ret, sum[i][j]);
				}
			} 
			return ret;
		}
		Node *find(LL pp) {
			if (ch[0]->plen >= pp) {
				return ch[0]->find(pp);
			} else if (ch[0]->plen + len >= pp) {
				return this;
			} else {
				return ch[1]->find(pp - ch[0]->plen - len);
			}
		}
		Node *min() {
			if (ch[0] != null) {
				return ch[0]->min();
			} else {
				return this;
			}
		}
	}p[N];
	inline void insert(LL pp, int a ,int b, int c, LL l) {
		p[++tot] = Node(l, a, b, c);
		Node *nw = p + tot;
		if (root != null) {
			Node *pos = root->find(pp);
			pos->splay(null); root = pos;
			int nlen = root->ch[0]->plen + root->len - pp, LEN = root->len, ls = root->ch[0] - p, rs = root->ch[1] - p;
			p[++tot] = Node(nlen, LEN? root->adv[0] / LEN: 0, LEN? root->adv[1] / LEN: 0, LEN? root->adv[2] / LEN: 0);
			*root = Node(LEN - nlen, LEN? root->adv[0] / LEN: 0, LEN? root->adv[1] / LEN: 0, LEN? root->adv[2] / LEN: 0);
			root->ch[0] = p + ls, root->ch[1] = p + rs;
			if (root->ch[1] != null) {
				root->ch[1]->min()->splay(root);
				p[tot].fa = root->ch[1];
				root->ch[1]->ch[0] = p + tot;
				nw->fa = p + tot;
				p[tot].ch[0] = nw;
				p[tot].maintain();
				root->ch[1]->maintain();
				root->maintain();
			} else {
				p[tot].fa = root;
				root->ch[1] = p + tot;
				nw->fa = p + tot;
				p[tot].ch[0] = nw;
				p[tot].maintain();
				root->maintain();
			}			
		} else {
			root = nw;
		}
	}
	inline LL query() {
		return root->ans();
	}
	inline void init() {
		null = root = p;
	}
};

int main() {
	Splay::init();
	int n; scanf("%d", &n);
	for (LL i = 1, LastAns = 0; i <= n; ++i) {
		LL pos, len, tmp, a, b, c;
		cin>>pos>>a>>b>>c>>len;
		Splay::insert(pos, a, b, c, len);
		tmp = Splay::query();
		printf("%lld\n", tmp - LastAns);
		LastAns = tmp;
	}
	return 0;
}

【BZOJ 4573】[ZJOI2016] 大森林

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4573
数据生成器:http://paste.ubuntu.com/24208883/
神犇题解Ⅰ:http://blog.csdn.net/werkeytom_ftd/article/details/56671440
神犇题解Ⅱ:http://sxy-cnyali.logdown.com/posts/1398090-zjoi2016

解题报告

这题似乎有三种做法?我们这里只讨论$LCT$的做法

首先将询问离线,对于每一次0/1号操作,都新建一个结点
并且挂到它之前的最后一个1号操作对应的节点下

我们考虑对于第$i$棵树的某个结点$j$
在最终形态中,其一定是在对在$i$树有效最后一个$1$号操作指定的点下面
所以我们对于一个$1$号操作的结点,若其生效了,那么将其整个子树全部移到指定结点
若其失效了,我们将其整个子树移到它之前的最晚一个$1$号操作对应的节点下
这样显然就可以回答询问了,搞几次$access$操作即可

于是问题变成如何动态维护一棵树,要求移动子树、询问根到某个点的路径上权值和
这个显然可以无脑$LCT$,于是我们就在$O(n \log n)$的时间复杂度内解决这个问题啦!

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 300009;

int n,m,num[N],l[N],r[N],last[N],to[N],ans[N],id[N];
vector<int> ins[N],del[N],q[N];

inline int read() {
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

class Link_Cut_Tree{
	struct Node{int val,sum,fa,ch[2];}p[N];
	int cnt;
	public:
		inline int NewNode(int v) {
			p[cnt+1].sum = p[cnt+1].val = v;
			return ++cnt;
		}
		inline void modify(int w, int t) {
			cut(num[w]); 
			if (t == 1) link(num[w], id[to[w]]);
			else link(num[w], last[w]);
		}
		inline int query(int x) {
			int u = id[l[N-x]], v = id[r[N-x]], ret;
			access(u); splay(u); ret = p[u].sum;
			x = access(v); splay(v); ret += p[v].sum;
			access(x); splay(x); ret -= p[x].sum << 1;
			return abs(ret);
		}
		inline void link(int a, int b) {
			splay(a); p[a].fa = b;
		}
		inline void cut(int x) {
			access(x); splay(x); 
			p[x].ch[0] = p[p[x].ch[0]].fa = 0;
			maintain(x); 
		}
	private:
		inline void maintain(int w) {
			p[w].sum = p[w].val + p[p[w].ch[0]].sum + p[p[w].ch[1]].sum;
		}
		inline bool IsRoot(int w) {
			return !p[w].fa || (p[p[w].fa].ch[0] != w && p[p[w].fa].ch[1] != w);
		}
		inline void rotate(int x) {
			int y=p[x].fa,z=p[y].fa,t=p[y].ch[1]==x;
			if (!IsRoot(y)) p[z].ch[p[z].ch[1]==y] = x;
			p[y].ch[t] = p[x].ch[t^1]; p[p[x].ch[t^1]].fa = y;
			p[x].ch[t^1] = y; p[x].fa = z; p[y].fa = x;
			maintain(y); maintain(x);
		}
		inline void splay(int x) {
			for (int f,ff;!IsRoot(x);) {
				f = p[x].fa; ff = p[f].fa;
				if (IsRoot(f)) rotate(x);
				else {
					if ((p[ff].ch[0]==f)^(p[f].ch[0]==x)) rotate(x),rotate(x);
					else rotate(f),rotate(x);
				}
			}
		}
		inline int access(int x) {
			for (int last=0;;last=x,x=p[x].fa) 
				if (x) splay(x), p[x].ch[1] = last, maintain(x);
				else return last;
		}
}lct;

int main() {
	n = read(); m = read();
	int pre = lct.NewNode(0); id[1] = lct.NewNode(1);
	lct.link(pre, id[1]); l[1] = 1; r[1] = n;
	for (int i=1,opt,ll,rr,x,tot=1;i<=m;i++) {
		if (!(opt=read())) {
			id[++tot] = lct.NewNode(1);
			l[tot] = read(); r[tot] = read();
			lct.link(id[tot], pre);
		} else if (opt == 1) {
			ll = read(); rr = read(); to[i] = x = read(); 
			ll = max(ll, l[x]); rr = min(rr, r[x]);
			if (ll <= rr) {
				ins[ll].push_back(i), del[rr].push_back(i);
				num[i] = lct.NewNode(0); lct.link(num[i], pre); 
				last[i] = pre; pre = num[i];
			} 
		} else {
			x = read(); l[N-i] = read(); r[N-i] = read();
			q[x].push_back(i);
		}
	}
	memset(ans,-1,sizeof(ans));
	for (int i=1;i<=n;i++) {
		for (int j=ins[i].size()-1;~j;j--) lct.modify(ins[i][j], 1);
		for (int j=q[i].size()-1;~j;j--) ans[q[i][j]] = lct.query(q[i][j]);
		for (int j=del[i].size()-1;~j;j--) lct.modify(del[i][j], -1);
	}
	for (int i=1;i<=m;i++) (~ans[i])? printf("%d\n",ans[i]),1: 0; 
	return 0;
}

【BZOJ 1895】[PKU3580] SuperMemo

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1895
数据生成器:http://paste.ubuntu.com/24163947/
神犇题解:http://blog.csdn.net/willinglive/article/details/41488487
原题链接:http://poj.org/problem?id=3580

解题报告

这就是个操作比较全的Splay的板
然而这个上一次写Splay是去年这时候的纸张写了一个下午,调了一个晚上QwQ

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
  
const int INF = 0x7fffffff;
const int N = 200009;
  
inline int read() {
    char c=getchar(); int ret=0,f=1;
    while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
    while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
    return ret*f;
}
  
class Splay{
    struct Node{int ch[2],val,mn,sz,fa,delta,rev;}p[N]; int cnt;
    public:
        inline Splay() { 
            cnt = 2; p[1].ch[1] = 2;
            p[1].val = p[1].mn = INF;
            p[2].val = p[2].mn = INF;
            p[1].sz = 2; p[2].sz = 1;
            p[1].fa = p[2].fa = 1;
        }
        inline void insert(int pos, int v) { ++pos;
            int w; splay(w=rank(1, pos), 1);
            int nw; splay(nw=rank(1, pos+1), w);
            p[nw].ch[0] = ++cnt; p[cnt].fa = nw;
            p[cnt].mn = p[cnt].val = v; p[cnt].sz = 1;
            maintain(nw); maintain(w); maintain(1);
        }
        inline void add(int l, int r, int v) { ++l; ++r;
            int w; splay(w=rank(1, l-1), 1);
            int nw; splay(nw=rank(1, r+1), w);
            p[p[nw].ch[0]].delta += v; 
            PushDown(p[nw].ch[0]); maintain(nw);
            maintain(w); maintain(1); 
        }
        inline int query(int l, int r) { ++l; ++r;
            int w; splay(w=rank(1, l-1), 1); 
            int nw; splay(nw=rank(1, r+1), w);
            return PushDown(p[nw].ch[0]), p[p[nw].ch[0]].mn;
        }
        inline void remove(int r) { ++r;
            int w; splay(w=rank(1, r-1), 1);
            int nw; splay(nw=rank(1, r+1), w);
            p[nw].ch[0] = 0; maintain(nw);
            maintain(w); maintain(1);
        } 
        inline void reverse(int l, int r) { ++l; ++r;
            int w; splay(w=rank(1, l-1), 1);
            int nw; splay(nw=rank(1, r+1), w);
            p[p[nw].ch[0]].rev ^= 1;
        }
        inline void Rotate(int l, int r, int t) {
            if (l==r||!(t%=((++r) - (++l) + 1))) return;
            int w; splay(w=rank(1, l-1), 1); 
            int nw; splay(nw=rank(1, r+1), w);
            int nnw; splay(nnw=rank(p[nw].ch[0], r-l-t+1), nw); 
            int nnnw; splay(nnnw=rank(p[nnw].ch[1], t), nnw); 
            p[nw].ch[0] = nnnw; p[nnnw].ch[1] = nnw; p[nnw].ch[1] = 0;
            p[nnw].fa = nnnw; p[nnnw].fa = nw;
            maintain(nnw); maintain(nnnw); 
        }
        inline void build(int r) {
            build(p[2].ch[0], 2, 1, r);
        }
    private:
        inline void PushDown(int w) {
            if (p[w].delta) {
                p[w].mn += p[w].delta; p[w].val += p[w].delta;
                p[p[w].ch[1]].delta += p[w].delta;
                p[p[w].ch[0]].delta += p[w].delta;
                p[w].delta = 0;
            }
            if (p[w].rev) {
                swap(p[w].ch[0], p[w].ch[1]); p[w].rev = 0;
                p[p[w].ch[0]].rev ^= 1; p[p[w].ch[1]].rev ^= 1;
            }
        }
        inline void maintain(int w) {
            p[w].mn = p[w].val; p[w].sz = p[p[w].ch[0]].sz + p[p[w].ch[1]].sz + 1;
            if (p[w].ch[0]) PushDown(p[w].ch[0]), p[w].mn = min(p[w].mn, p[p[w].ch[0]].mn);
            if (p[w].ch[1]) PushDown(p[w].ch[1]), p[w].mn = min(p[w].mn, p[p[w].ch[1]].mn); 
        }
        inline void rotate(int w) {
            int f=p[w].fa,t=p[f].ch[1]==w,ff=p[f].fa; 
            p[f].ch[t] = p[w].ch[t^1]; p[p[w].ch[t^1]].fa = f;
            p[w].ch[t^1] = f; p[w].fa = p[f].fa; p[f].fa = w; 
            if (ff != f) p[ff].ch[p[ff].ch[1]==f] = w;
            maintain(f); maintain(w);
        }
        inline void splay(int w, int pur) { 
            if (w == pur) return;
            for (int f,ff;f=p[w].fa,p[w].fa!=pur;) {
                ((ff=p[f].fa) == pur)? rotate(w):
                (((p[f].ch[1]==w)^(p[ff].ch[1]==f))?rotate(w),rotate(f):rotate(f),rotate(w));
            }
        }
        int rank(int w, int t) {
            PushDown(w); if (t<=0) return w; int szt = p[p[w].ch[0]].sz;
            if (szt >= t) return rank(p[w].ch[0], t);
            else if (szt + 1 == t) return w;
            else return rank(p[w].ch[1], t-1-szt);
        }
        void build(int &w, int f, int l, int r) {
            int mid = l + r >> 1; p[w=++cnt].fa = f; p[w].sz = 1; p[w].mn = INF;
            if (l < mid) build(p[w].ch[0], w, l, mid-1), p[w].sz += p[p[w].ch[0]].sz, p[w].mn = min(p[w].mn, p[p[w].ch[0]].mn);
            p[w].mn = min(p[w].mn, p[w].val = read());
            if (mid < r) build(p[w].ch[1], w, mid+1, r), p[w].sz += p[p[w].ch[1]].sz, p[w].mn = min(p[w].mn, p[p[w].ch[1]].mn);
        }
}SP; 
  
int main() {
    int n = read(); char opt[10]; SP.build(n);
    for (int m=read(),l,r,x;m;--m) {
        scanf("%s",opt+1);
        if (opt[1] == 'A') {
            l = read(); r = read();
            SP.add(l, r, read());
        } else if (opt[1] == 'R' && opt[4] == 'E') {
            l = read(); r = read();
            SP.reverse(l, r);
        } else if (opt[1] == 'R') {
            l = read(); r = read();
            SP.Rotate(l, r, read());
        } else if (opt[1] == 'I') {
            l = read(); r = read();
            SP.insert(l, r);
        } else if (opt[1] == 'D') {
            SP.remove(read());
        } else {
            l = read(); r = read();
            printf("%d\n",SP.query(l,r));
        } 
    }
    return 0;
}

【模板库】Splay

参考例题:http://www.lydsy.com/JudgeOnline/problem.php?id=1895

#include<bits/stdc++.h>
#define LL long long
using namespace std;
  
const int INF = 0x7fffffff;
const int N = 200009;
  
inline int read() {
    char c=getchar(); int ret=0,f=1;
    while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
    while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
    return ret*f;
}
  
class Splay{
    struct Node{int ch[2],val,mn,sz,fa,delta,rev;}p[N]; int cnt;
    public:
        inline Splay() { //init the splay and place begining(1) and ending(2) of the sequence
            cnt = 2; p[1].ch[1] = 2;
            p[1].val = p[1].mn = INF;
            p[2].val = p[2].mn = INF;
            p[1].sz = 2; p[2].sz = 1;
            p[1].fa = p[2].fa = 1;
        }
        inline void insert(int pos, int v) { ++pos; //insert a new node with value v as ths (pos + 1) node
            int w; splay(w=rank(1, pos), 1);
            int nw; splay(nw=rank(1, pos+1), w);
            p[nw].ch[0] = ++cnt; p[cnt].fa = nw;
            p[cnt].mn = p[cnt].val = v; p[cnt].sz = 1;
            maintain(nw); maintain(w); maintain(1);
        }
        inline void add(int l, int r, int v) { ++l; ++r; //add value v to elements of range[l,r]
            int w; splay(w=rank(1, l-1), 1);
            int nw; splay(nw=rank(1, r+1), w);
            p[p[nw].ch[0]].delta += v; 
            PushDown(p[nw].ch[0]); maintain(nw);
            maintain(w); maintain(1); 
        }
        inline int query(int l, int r) { ++l; ++r; //query the min element in range[l,r]
            int w; splay(w=rank(1, l-1), 1); 
            int nw; splay(nw=rank(1, r+1), w);
            return PushDown(p[nw].ch[0]), p[p[nw].ch[0]].mn;
        }
        inline void remove(int r) { ++r; //remove the r node
            int w; splay(w=rank(1, r-1), 1);
            int nw; splay(nw=rank(1, r+1), w);
            p[nw].ch[0] = 0; maintain(nw);
            maintain(w); maintain(1);
        } 
        inline void reverse(int l, int r) { ++l; ++r; //reverse the elements in range[l,r]
            int w; splay(w=rank(1, l-1), 1);
            int nw; splay(nw=rank(1, r+1), w);
            p[p[nw].ch[0]].rev ^= 1;
        }
        inline void Rotate(int l, int r, int t) { //rotate the elements in range[l,r] t steps
            if (l==r||!(t%=((++r) - (++l) + 1))) return;
            int w; splay(w=rank(1, l-1), 1); 
            int nw; splay(nw=rank(1, r+1), w);
            int nnw; splay(nnw=rank(p[nw].ch[0], r-l-t+1), nw); 
            int nnnw; splay(nnnw=rank(p[nnw].ch[1], t), nnw); 
            p[nw].ch[0] = nnnw; p[nnnw].ch[1] = nnw; p[nnw].ch[1] = 0;
            p[nnw].fa = nnnw; p[nnnw].fa = nw;
            maintain(nnw); maintain(nnnw); 
        }
    private:
        inline void PushDown(int w) {
            if (p[w].delta) {
                p[w].mn += p[w].delta; p[w].val += p[w].delta;
                p[p[w].ch[1]].delta += p[w].delta;
                p[p[w].ch[0]].delta += p[w].delta;
                p[w].delta = 0;
            }
            if (p[w].rev) {
                swap(p[w].ch[0], p[w].ch[1]); p[w].rev = 0;
                p[p[w].ch[0]].rev ^= 1; p[p[w].ch[1]].rev ^= 1;
            }
        }
        inline void maintain(int w) {
            p[w].mn = p[w].val; p[w].sz = p[p[w].ch[0]].sz + p[p[w].ch[1]].sz + 1;
            if (p[w].ch[0]) PushDown(p[w].ch[0]), p[w].mn = min(p[w].mn, p[p[w].ch[0]].mn);
            if (p[w].ch[1]) PushDown(p[w].ch[1]), p[w].mn = min(p[w].mn, p[p[w].ch[1]].mn); 
        }
        inline void rotate(int w) { //rotate w to its father
            int f=p[w].fa,t=p[f].ch[1]==w,ff=p[f].fa; 
            p[f].ch[t] = p[w].ch[t^1]; p[p[w].ch[t^1]].fa = f;
            p[w].ch[t^1] = f; p[w].fa = p[f].fa; p[f].fa = w; 
            if (ff != f) p[ff].ch[p[ff].ch[1]==f] = w;
            maintain(f); maintain(w);
        }
        inline void splay(int w, int pur) { //splay w to pur's son
            if (w == pur) return;
            for (int f,ff;f=p[w].fa,p[w].fa!=pur;) {
                ((ff=p[f].fa) == pur)? rotate(w):
                (((p[f].ch[1]==w)^(p[ff].ch[1]==f))?rotate(w),rotate(f):rotate(f),rotate(w));
            }
        }
        int rank(int w, int t) { //function rank is needed to be called before each splay operation to push down tags
            PushDown(w); if (t<=0) return w; int szt = p[p[w].ch[0]].sz;
            if (szt >= t) return rank(p[w].ch[0], t);
            else if (szt + 1 == t) return w;
            else return rank(p[w].ch[1], t-1-szt);
        }
}SP; 
  
int main() {
    int n = read(); char opt[10]; 
    for (int i=1;i<=n;i++) SP.insert(i-1, read());
    for (int m=read(),l,r,x;m;--m) {
        scanf("%s",opt+1);
        if (opt[1] == 'A') {
            l = read(); r = read();
            SP.add(l, r, read());
        } else if (opt[1] == 'R' && opt[4] == 'E') {
            l = read(); r = read();
            SP.reverse(l, r);
        } else if (opt[1] == 'R') {
            l = read(); r = read();
            SP.Rotate(l, r, read());
        } else if (opt[1] == 'I') {
            l = read(); r = read();
            SP.insert(l, r);
        } else if (opt[1] == 'D') {
            SP.remove(read());
        } else {
            l = read(); r = read();
            printf("%d\n",SP.query(l,r));
        } 
    }
    return 0;
}

【日常小测】市场

相关链接

题目传送门:https://ly.men.ci/problem/196

题目大意

搞一个数据结构来维护一个长度为$n(n \le 10^5)$的序列。
并进行$m(m \le 10^5)$个操作,操作分为以下四种:

  1. 区间加$c(-10^4 \le c \le 10^4)$
  2. 区间除$d$。即对于单个元素$a_i$,除以$d$后变为$\lfloor \frac{a_i}{d} \rfloor$
  3. 询问区间和
  4. 询问区间最值

解题报告

考虑将所有的相邻的并且值相同的位置合成一个块
考虑一次修改操作最多增加两个块,于是总的块数不会超过$n+m$
那么对于操作二,我们暴力应用到区间的每一个块上
因为每一个块最多进行$\log val$次的操作二就会消失
所以总的操作次数不会超过$O ((n+m) \log (10^4))$

现在考虑具体实现
不嫌麻烦的话,我们可以使用$Splay$。脑袋里想想还是很好写的
要好写一点的话,我们就用线段树,记录一下一个点的子树中所有的值是否相等

相关拓展

这种将相同值合并到一起来保证复杂度的题目还在雅礼集训的时候见过一次啊
当时是要求将编号$l \to r$的结点的父亲全部设为$x$,然后单点修改权值,查询某个点的子树和
也是将$fa$相同的点搞在一起,然后用$Splay$维护一下