这是一级标题
这是二级标题
这是三级标题
这是四级标题
这是五级标题
这是六级标题
| 公 | 式 |
|---|---|
| 测 | 试 |
$\sum_{i=1}^{n} a_i^2x_i$
$\prod_{i=1}^{n} a_i^2x_i$
另外
这是
UOJ #218的题解
维护一颗主席树
火车入栈相当于区间修改，弹栈相当于返回历史版本
维护线段树区间求和
extra RE啦卡卡内存应该可过，算啦不写了
markdown测试与UOJ#218
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
const int maxn = 600005;
const int maxm = 40000007;
int tt[maxm],ls[maxm],tag[maxm],rs[maxm];
int tg[maxn<<2],sum[maxn<<2],sz,rt[maxn<<1],a[maxn<<1];
int n,m,ty;
int read(){
int t=0,f=1;char c=getchar();
while (c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
while ('0'<=c&&c<='9'){t=t*10+c-'0';c=getchar();}
return t*f;
}
void merge(int k) {
if (tag[k]==-1) return;
if (!ls[k]) ls[k]=++sz;
if (!rs[k]) rs[k]=++sz;
tag[ls[k]]=tag[rs[k]]=tt[ls[k]]=tt[rs[k]]=tag[k];
tag[k]=-1;
}
void modify(int &k,int l,int r,int rt,int tl,int tr,int v){
k=++sz;tag[k]=-1;
if (tl<=l&&tr>=r){
tag[k]=tt[k]=v;
return;
}
merge(rt);
int mid=(l+r)>>1;
ls[k]=ls[rt];rs[k]=rs[rt];
if(mid>=tl)modify(ls[k],l,mid,ls[rt],tl,tr,v);
if(mid<tr)modify(rs[k],mid+1,r,rs[rt],tl,tr,v);
}
int query(int l,int r,int rt,int pos){
if(!rt||l==r) return tt[rt];
merge(rt);
int mid=(l+r)>>1;
if(pos<=mid) return query(l,mid,ls[rt],pos);
else return query(mid+1,r,rs[rt],pos);
}
void pushdown(int l,int r,int rt){
if(tg[rt]==-1||l==r) return;
tg[rt<<1]=tg[rt<<1|1]=tg[rt];
int mid=(l+r)>>1;
sum[rt<<1]=tg[rt]*(mid-l+1);
sum[rt<<1|1]=tg[rt]*(r-mid);
tg[rt]=-1;
}
void modify2(int l,int r,int rt,int tl,int tr,int v){
pushdown(l,r,rt);
if(tl<=l&&tr>=r){
tg[rt]=v;sum[rt]=(r-l+1)*v;
pushdown(l,r,rt);
return;
}
int mid=(l+r)>>1;
if(mid>=tl)modify2(l,mid,rt<<1,tl,tr,v);
if(mid<tr)modify2(mid+1,r,rt<<1|1,tl,tr,v);
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
int getsum(int l,int r,int rt,int tl,int tr){
pushdown(l,r,rt);
if(tl<=l&&tr>=r){
return sum[rt];
}
int mid=(l+r)>>1;
int ret=0;
if(mid>=tl)ret+=getsum(l,mid,rt<<1,tl,tr);
if(tr>mid)ret+=getsum(mid+1,r,rt<<1|1,tl,tr);
return ret;
}
int main(){
n=read();m=read();ty=read();
int ans=0;
for(int i=1;i<=m;i++){
rt[i]=rt[i-1];
int opt=read(),l=read();l=(l+ty*ans)%n+1;
if (opt==1) {
int r=read();r=(r+ty*ans)%n+1;
if (l>r) std::swap(l,r);
printf("%d\n",ans=getsum(1,n,1,l,r));
}
else if (opt==2){
int x=query(1,n,rt[i],l);
if(x){
int y=query(1,n,rt[x-1],l);
modify(rt[i],1,n,rt[i],l,l,y);
modify2(1,n,1,l,l,a[y]);
}
continue;
}
else{
int r=read();r=(r+ty*ans)%n+1;
if (l>r) std::swap(l,r);
a[i]=read();
modify(rt[i],1,n,rt[i],l,r,i);
modify2(1,n,1,l,r,a[i]);
}
}
return 0;
}