题意简述
有个栈,编号为
到
。有
个操作,如下三种:
1 l r : 计算第到第
个栈的栈顶元素之和。
2 l : 第个栈弹出栈顶元素,如果不存在则不执行。
3 l r x : 第到第
个栈都把
压栈。
强制在线。
算法讨论
一开始一直在想是不是要线段树上弄一些奇形怪状的标记。
看过标算感觉有点神,而且挺小清新的。
考虑栈的性质。退栈就相当与撤销修改操作嘛。
考虑建立可持久化线段树,维护每个位置最近的修改时间和栈顶的权值。
那么区间压栈就相当于区间覆盖。注意,可持久化线段树上区间覆盖较难下传标记,考虑到只有单点查询,标记永久化即可。单点弹栈的话我们可以去找到最近的修改时间-1的时间点查询到上次修改的信息,并直接拿过来覆盖到这个时间点上就相当于我们撤销了一次修改。
对于询问,我们可以另建一棵普通线段树,上面维护所有位置的栈顶元素。维护时一起修改一下就好了。
时间复杂度和空间复杂度均为,空间的常数有点大。
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 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 |
#include <set> #include <map> #include <queue> #include <ctime> #include <cmath> #include <cstdio> #include <vector> #include <string> #include <cctype> #include <bitset> #include <cstring> #include <cstdlib> #include <utility> #include <iostream> #include <algorithm> #define REP(i,a,b) for(int i=(a);i<=(b);i++) #define PER(i,a,b) for(int i=(a);i>=(b);i--) #define RVC(i,S) for(int i=0;i<(S).size();i++) #define RAL(i,u) for(int i=fr[u];i!=-1;i=e[i].next) using namespace std; typedef long long LL; typedef pair<int,int> pii; template<class T> inline void read(T& num) { bool start=false,neg=false; char c; num=0; while((c=getchar())!=EOF) { if(c=='-') start=neg=true; else if(c>='0' && c<='9') { start=true; num=num*10+c-'0'; } else if(start) break; } if(neg) num=-num; } /*============ Header Template ============*/ const int maxn=(int)(5e5)+5; int rt[maxn]; int ls[maxn*120],rs[maxn*120]; int vi[maxn*120],ci[maxn*120],ti[maxn*120]; namespace Tmp { int idx; void M(int& x,int l,int r,int s,int t,int v,int c,int T) { int px=x; x=++idx; vi[x]=vi[px];ci[x]=ci[px];ti[x]=ti[px]; ls[x]=ls[px];rs[x]=rs[px]; if(s<=l && r<=t) { vi[x]=v;ci[x]=c;ti[x]=T;return; } int mid=(l+r)>>1; if(s<=mid) M(ls[x],l,mid,s,t,v,c,T); if(mid <t) M(rs[x],mid+1,r,s,t,v,c,T); } void Q(int x,int l,int r,int ps,int& v,int& c,int& T) { if(ti[x]>T) v=vi[x],c=ci[x],T=ti[x]; if(l==r) return; int mid=(l+r)>>1; if(ps<=mid) Q(ls[x],l,mid,ps,v,c,T); else Q(rs[x],mid+1,r,ps,v,c,T); } } namespace Ans { int su[maxn<<2]; int ci[maxn<<2]; inline void Mi(int x,int l,int r,int v) { ci[x]=v;su[x]=(r-l+1)*v; } inline void pd(int x,int l,int r) { if(ci[x]) { int mid=(l+r)>>1; Mi(x<<1,l,mid,ci[x]); Mi(x<<1|1,mid+1,r,ci[x]); ci[x]=0; } } inline void pu(int x) { su[x]=su[x<<1]+su[x<<1|1]; } void M(int x,int l,int r,int s,int t,int v) { if(s<=l && r<=t) { Mi(x,l,r,v);return; } pd(x,l,r);int mid=(l+r)>>1; if(s<=mid) M(x<<1,l,mid,s,t,v); if(mid <t) M(x<<1|1,mid+1,r,s,t,v); pu(x); } int Q(int x,int l,int r,int s,int t) { if(s<=l && r<=t) return su[x]; pd(x,l,r);int mid=(l+r)>>1,res=0; if(s<=mid) res+=Q(x<<1,l,mid,s,t); if(mid <t) res+=Q(x<<1|1,mid+1,r,s,t); return res; } } int main() { int n,m,ty; read(n);read(m);read(ty); int la=0,cnt=0; ++cnt; Tmp::M(rt[cnt],1,n,1,n,0,cnt,cnt); REP(i,1,m) { int opt,l,r,x; read(opt); if(opt==1) { read(l);read(r); l=(l+la*ty)%n+1; r=(r+la*ty)%n+1; if(l>r) swap(l,r); printf("%d\n",la=Ans::Q(1,1,n,l,r)); } else if(opt==2) { read(l); l=(l+la*ty)%n+1; int v=0,c=0,T=0; Tmp::Q(rt[cnt],1,n,l,v,c,T); int nc=c;v=c=T=0;if(nc==1) continue; Tmp::Q(rt[nc-1],1,n,l,v,c,T); ++cnt;rt[cnt]=rt[cnt-1]; Tmp::M(rt[cnt],1,n,l,l,v,c,cnt); Ans::M(1,1,n,l,l,v); } else if(opt==3) { read(l);read(r);read(x); l=(l+la*ty)%n+1; r=(r+la*ty)%n+1; if(l>r) swap(l,r); ++cnt;rt[cnt]=rt[cnt-1]; Tmp::M(rt[cnt],1,n,l,r,x,cnt,cnt); Ans::M(1,1,n,l,r,x); } } return 0; } |