Tag: Persistent Segment Tree

题目传送门：http://uoj.ac/problem/218
数据生成器：http://paste.ubuntu.com/20456908/

这一道题目，考试的时候，还是想要A掉来着，结果wa得只剩10分QAQ
™我的自定义测试，那么大的数据都没有wa

考试的时候，我的做法是：
单独一棵线段树用来处理询问
然后再用一个二维线段树来维护堆栈
第一维是时间，用来二分最近最近的有效操作
第二维是车站，用来支持二分的查询动作
时间复杂度:O(nlog^2(n))

std的做法是：
任然单独搞一棵线段树来对付询问
对于操作，直接上函数式线段树QAQ
时间复杂度:O(nlogn)

至今都觉得还是我的做法最自然
但他们都说函数式线段树最自然QAQ

#include<iostream>
#include<cstdio>
using namespace std;

const int MAXN = 500000+9;

int n,m,ty,last_ans,arr[MAXN];

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

namespace Segment_Tree{
	#define SEG Segment_Tree
	const int N = MAXN*4;
	int tag[N],sum[N],tm[N],ans_tmp,L,R,DEL;
	
	inline void push_down(int w, int l, int r, int mid){
		tag[w*2] = tag[w*2+1] = tag[w];
		sum[w*2] = (mid-l)*arr[tag[w]];
		sum[w*2+1] = (r-mid+1)*arr[tag[w]];
		tag[w] = 0;
	}
	
	void query(int w, int l, int r){
		if (L <= l && r <= R) ans_tmp += sum[w];
		else {
			int mid = (l + r + 1) / 2;
			if (tag[w]) push_down(w,l,r,mid);
			if (L < mid) query(w*2,l,mid-1);
			if (R >= mid) query(w*2+1,mid,r);
		}
	}inline int query(int l, int r){ans_tmp=0;L=l,R=r;query(1,1,n);return ans_tmp;}
	
	void Modify(int w, int l, int r){
		if (L <= l && r <= R) tag[w] = DEL, sum[w] = (r-l+1)*arr[DEL];
		else {
			int mid = (l + r + 1) / 2;
			if (tag[w]) push_down(w,l,r,mid);
			if (L < mid) Modify(w*2,l,mid-1);
			if (R >= mid) Modify(w*2+1,mid,r);
			sum[w] = sum[w*2] + sum[w*2+1];
		}
	}inline void modify(int l, int r, int del){L=l,R=r,DEL=del;Modify(1,1,n);}
	
	inline int index(int pos){
		int w = 1, l = 1, r = n, mid;
		while (l < r) {
			if (tag[w]) return tag[w];
			else {
				mid = (l + r + 1) / 2;
				if (pos < mid) w = w*2, r = mid-1;
				else w = w*2+1, l = mid;
			}
		}
		return tag[w];
	}
}; 

namespace Persistent_Segment_Tree{
	#define PST Persistent_Segment_Tree
	const int N = 20000000;
	int tag[N],root[N],ch[N][2],tot,cnt,L,R,DEL;
	
	inline int query(int tm, int pos) {
		if (tm < 1) return 0;
		else {
			int w = root[tm], l=1, r=n, mid;
			while (l < r) {
				if (tag[w]) return tag[w];
				else {
					mid = (l + r + 1) / 2;
					if (pos < mid) w = ch[w][0], r = mid-1;
					else w = ch[w][1], l = mid;
				}
			}
			return tag[w];
		}
	}
	
	inline void push_down(int w){
		for (int i=0;i<=1;i++) if (!ch[w][i]) ch[w][i] = ++cnt;
		for (int i=0;i<=1;i++) tag[ch[w][i]] = tag[w];
		tag[w] = 0;
	}
	
	void Modify(int pre, int &w, int l, int r, int tg){
		w = ++cnt; ch[w][1] = ch[pre][1]; 
		ch[w][0] = ch[pre][0]; tag[w] = tg?tg:tag[pre];
		if (L <= l && r <= R) tag[w] = DEL;
		else {
			int mid = (l + r + 1) / 2; 
			if (L < mid) Modify(ch[pre][0],ch[w][0],l,mid-1,tag[w]);
			else if (tag[w]) ch[w][0] = ++cnt, tag[cnt] = tag[w];
			if (mid <= R) Modify(ch[pre][1],ch[w][1],mid,r,tag[w]);
			else if (tag[w]) ch[w][1] = ++cnt, tag[cnt] = tag[w];
			tag[w] = 0;
		}
	}
	
	inline int modify(int l, int r, int val, bool type){
		L = l, R = r, DEL = val; 
		Modify(root[tot], root[(tot+type)], 1, n, 0);
		tot += type; return tot;
	}
};

int main(){
	scanf("%d%d%d",&n,&m,&ty);
	for (int i=1,type,l,r,del;i<=m;i++){
		scanf("%d",&type);
		if (type == 1) {
			l = read(); r = read();
			if (l > r) swap(l, r);
			printf("%d\n",last_ans=SEG::query(l,r));
		} else if (type == 2) {
			l = read();
			int tmp = SEG::index(l);
			int nv = PST::query(tmp-1,l);
			PST::modify(l,l,nv,0);
			SEG::modify(l,l,nv);
		} else {
			l = read(); r = read(); scanf("%d",&del);
			if (l > r) swap(l, r); 
			int tmp = PST::modify(l,r,PST::tot+1,1);
			arr[tmp] = del;
			SEG::modify(l, r, tmp);
		}
	}
	return 0;
}