#46. 【清华集训2014】玄学
大意
维护长度$10^5$的序列，有以下操作$5 imes 10^6$ 次
- 修改：对于$[l,r]$，的所有$a_i$变成$(A imes a_i) + B$
- 查询：假如时间轴上$[l,r]$之间的修改存在，其他修改不存在，那么$a_k$的值是多少
题解
- 考虑在时间轴上面维护线段树，线段树上每个节点维护一个$vector$，用这个$vector$维护这个时间段的序列$a$，里面是一些按照$l,r$排序的四元组${a,b,l,r}$表示下标为$[l,r]$的$a_i$的最终操作$a,b$
- 这里有个叫做"二进制分组"的优化，就是当一个线段树节点，它的子节点都塞满之后，并不会再有修改操作进入，那么我们合并这两个节点的信息，归并排序，并且块数不会太多
- 线段树复杂度加个二分，$O(nlog^2n)$
代码
#include<bits/stdc++.h>
#define FOR(i,a,b) for (register int i=(a);i<=(b);i++)
#define pb push_back
using namespace std;
typedef long long ll;
const int N=6e5+5;
const int T=600000;
int type,n,mod,q,a[N],time_now=0,f[N<<2];
int opt,tmp1,tmp2,tmp3,tmp4,ans;
struct data
{
int a,b,l,r;
}tmp_node;
inline data merge(data x,data y)
{
data ret;
ret.a=1LL*x.a*y.a%mod;
ret.b=(1LL*x.b*y.a%mod+y.b)%mod;
ret.l=max(x.l,y.l);
ret.r=min(x.r,y.r);
return ret;
}
vector <data> tr[N<<2];
inline int read()
{
int x=0,f=1;
char c=getchar();
while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
while (c>='0'&&c<='9') {x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return f*x;
}
inline void write(int x)
{
if (x<0) putchar('-'),x=-x;
if (x>9) write(x/10);
putchar(x%10+'0');
return;
}
#define mid ((l+r)>>1)
#define lson p<<1,l,mid
#define rson p<<1|1,mid+1,r
inline void UP(int p)
{
tr[p].clear();
int ls=p<<1,rs=p<<1|1,siz1=tr[ls].size(),siz2=tr[rs].size();
data tmp;
for (register int i=0,j=0,now=1;i<siz1&&j<siz2;)
{
tmp=merge(tr[ls][i],tr[rs][j]);
tr[p].pb(tmp);
if (tr[ls][i].r==tmp.r) i++;
if (tr[rs][j].r==tmp.r) j++;
}
f[p]=1;
return;
}
inline void MD(int p,int l,int r,int k,data v)
{
if (l==r)
{
if (v.l>1) tr[p].pb((data){1,0,1,v.l-1});
tr[p].pb(v);
if (v.r<n) tr[p].pb((data){1,0,v.r+1,n});
f[p]=1;
return;
}
if (k<=mid) MD(lson,k,v);
else MD(rson,k,v);
if (f[p<<1]&&f[p<<1|1]&&!f[p]) UP(p);
return;
}
inline data QR(int p,int l,int r,int L,int R,int k)
{
if (L<=l&&r<=R)
{
int LL=0,RR=tr[p].size()-1,MID;
while (LL<=RR)
{
MID=(LL+RR)>>1;
if (tr[p][MID].l<=k&&k<=tr[p][MID].r) return tr[p][MID];
if (k<tr[p][MID].l) RR=MID-1;
else if (tr[p][MID].r<k) LL=MID+1;
}
}
data ret;
ret=(data){1,0,1,T};
if (L<=mid) ret=merge(ret,QR(lson,L,R,k));
if (R>mid) ret=merge(ret,QR(rson,L,R,k));
return ret;
}
#undef mid
#undef lson
#undef rson
int main()
{
type=read();
n=read(),mod=read();
FOR(i,1,n) a[i]=read();
q=read();
while (q--)
{
opt=read(),tmp1=read(),tmp2=read(),tmp3=read();
if (opt==1)
{
tmp4=read();
if (type&1) tmp1^=ans,tmp2^=ans;
tmp_node=(data){tmp3,tmp4,tmp1,tmp2};
++time_now;
MD(1,1,T,time_now,tmp_node);
}
else
{
if (type&1) tmp1^=ans,tmp2^=ans,tmp3^=ans;
tmp_node=QR(1,1,T,tmp1,tmp2,tmp3);
ans=(1LL*tmp_node.a*a[tmp3]%mod+tmp_node.b)%mod;
write(ans),putchar('
');
}
}
return 0;
}
1 #include<bits/stdc++.h> 2 #define FOR(i,a,b) for (register int i=(a);i<=(b);i++) 3 #define pb push_back 4 using namespace std; 5 typedef long long ll; 6 const int N=6e5+5; 7 const int T=600000; 8 int type,n,mod,q,a[N],time_now=0,f[N<<2]; 9 int opt,tmp1,tmp2,tmp3,tmp4,ans; 10 struct data 11 { 12 int a,b,l,r; 13 }tmp_node; 14 inline data merge(data x,data y) 15 { 16 data ret; 17 ret.a=1LL*x.a*y.a%mod; 18 ret.b=(1LL*x.b*y.a%mod+y.b)%mod; 19 ret.l=max(x.l,y.l); 20 ret.r=min(x.r,y.r); 21 return ret; 22 } 23 vector <data> tr[N<<2]; 24 inline int read() 25 { 26 int x=0,f=1; 27 char c=getchar(); 28 while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} 29 while (c>='0'&&c<='9') {x=(x<<1)+(x<<3)+c-'0';c=getchar();} 30 return f*x; 31 } 32 inline void write(int x) 33 { 34 if (x<0) putchar('-'),x=-x; 35 if (x>9) write(x/10); 36 putchar(x%10+'0'); 37 return; 38 } 39 #define mid ((l+r)>>1) 40 #define lson p<<1,l,mid 41 #define rson p<<1|1,mid+1,r 42 inline void UP(int p) 43 { 44 tr[p].clear(); 45 int ls=p<<1,rs=p<<1|1,siz1=tr[ls].size(),siz2=tr[rs].size(); 46 data tmp; 47 for (register int i=0,j=0,now=1;i<siz1&&j<siz2;) 48 { 49 tmp=merge(tr[ls][i],tr[rs][j]); 50 tr[p].pb(tmp); 51 if (tr[ls][i].r==tmp.r) i++; 52 if (tr[rs][j].r==tmp.r) j++; 53 } 54 f[p]=1; 55 return; 56 } 57 inline void MD(int p,int l,int r,int k,data v) 58 { 59 if (l==r) 60 { 61 if (v.l>1) tr[p].pb((data){1,0,1,v.l-1}); 62 tr[p].pb(v); 63 if (v.r<n) tr[p].pb((data){1,0,v.r+1,n}); 64 f[p]=1; 65 return; 66 } 67 if (k<=mid) MD(lson,k,v); 68 else MD(rson,k,v); 69 if (f[p<<1]&&f[p<<1|1]&&!f[p]) UP(p); 70 return; 71 } 72 inline data QR(int p,int l,int r,int L,int R,int k) 73 { 74 if (L<=l&&r<=R) 75 { 76 int LL=0,RR=tr[p].size()-1,MID; 77 while (LL<=RR) 78 { 79 MID=(LL+RR)>>1; 80 if (tr[p][MID].l<=k&&k<=tr[p][MID].r) return tr[p][MID]; 81 if (k<tr[p][MID].l) RR=MID-1; 82 else if (tr[p][MID].r<k) LL=MID+1; 83 } 84 } 85 data ret; 86 ret=(data){1,0,1,T}; 87 if (L<=mid) ret=merge(ret,QR(lson,L,R,k)); 88 if (R>mid) ret=merge(ret,QR(rson,L,R,k)); 89 return ret; 90 } 91 #undef mid 92 #undef lson 93 #undef rson 94 95 int main() 96 { 97 type=read(); 98 n=read(),mod=read(); 99 FOR(i,1,n) a[i]=read(); 100 q=read(); 101 while (q--) 102 { 103 opt=read(),tmp1=read(),tmp2=read(),tmp3=read(); 104 if (opt==1) 105 { 106 tmp4=read(); 107 if (type&1) tmp1^=ans,tmp2^=ans; 108 tmp_node=(data){tmp3,tmp4,tmp1,tmp2}; 109 ++time_now; 110 MD(1,1,T,time_now,tmp_node); 111 } 112 else 113 { 114 if (type&1) tmp1^=ans,tmp2^=ans,tmp3^=ans; 115 tmp_node=QR(1,1,T,tmp1,tmp2,tmp3); 116 ans=(1LL*tmp_node.a*a[tmp3]%mod+tmp_node.b)%mod; 117 write(ans),putchar(' '); 118 } 119 } 120 return 0; 12