题目传送门: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;
}