一开始脑子进水了、把这题想简单了、复杂度算错了、每次都用nlogn的时间修改、而且还狂写STL、然后就直播自爆8小时QAQ。
先挂个5分代码。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
using namespace std;
#define rep(i,j,k) for(i=j;i<=k;++i)
#define per(i,j,k) for(i=j;i>=k;--i)
#define pii pair<int,int>
#define mkp make_pair
#define X first
#define Y second
#define LL long long
LL n,M,m,w[100005],mx,ans;
struct MODIFY{LL I,J,A,B;}mdf0,sb;
vector<MODIFY>T[7000000];
LL qA,qB;
void write(LL l,LL r,LL num){
printf("%lld: ",num);
vector<MODIFY>::iterator ii;
for(ii=T[num].begin();ii!=T[num].end();++ii)
printf("%lld %lld %lld %lld ",ii->I,ii->J,ii->A,ii->B);
puts("");
if(l==r)return;
LL mid=l+r>>1;
write(l,mid,num<<1);write(mid+1,r,num<<1|1);
}
bool cmp1(MODIFY x,MODIFY y){
return x.I<y.I;
}
bool cmp2(MODIFY x,MODIFY y){
return x.J<y.J;
}
void build(LL l,LL r,LL num){
T[num].push_back(mdf0);T[num].push_back(sb);
if(l==r)return;
LL mid=l+r>>1LL;
build(l,mid,num<<1LL),build(mid+1LL,r,num<<1LL|1LL);
}
void ins(MODIFY in,LL x,LL l,LL r,LL num){
vector<MODIFY>::iterator ll,rr,ii;
ll=--upper_bound(T[num].begin(),T[num].end(),(MODIFY){in.I,0LL,0LL,0LL},cmp1);
LL tmpi=ll->I,tmpj=ll->J,tmpa=ll->A,tmpb=ll->B;
if(tmpi<in.I)T[num].insert(ll,(MODIFY){tmpi,in.I-1,tmpa,tmpb});
if(tmpj>=in.J){
rr=upper_bound(T[num].begin(),T[num].end(),(MODIFY){tmpi,0LL,0LL,0LL},cmp1);
if(tmpj>in.J)T[num].insert(rr,(MODIFY){in.J+1,tmpj,tmpa,tmpb});
rr=lower_bound(T[num].begin(),T[num].end(),(MODIFY){0LL,tmpj,0LL,0LL},cmp2);
*rr=(MODIFY){in.I,in.J,in.A*tmpa%M,(in.B+in.A*tmpb)%M};
}
else{
rr=lower_bound(T[num].begin(),T[num].end(),(MODIFY){0LL,in.J,0LL,0LL},cmp2);
if(tmpj>in.J)T[num].insert(rr,(MODIFY){in.J+1,tmpj,tmpa,tmpb});
ll=--upper_bound(T[num].begin(),T[num].end(),(MODIFY){tmpi,0LL,0LL,0LL},cmp1);
rr=lower_bound(T[num].begin(),T[num].end(),(MODIFY){0LL,in.J,0LL,0LL},cmp2);
*ll=(MODIFY){in.I,ll->J,in.A*ll->A%M,(in.B+in.A*ll->B)%M};
*rr=(MODIFY){rr->I,in.J,in.A*rr->A%M,(in.B+in.A*rr->B)%M};
for(ii=++ll;ii!=rr;++ii)
*ii=(MODIFY){ii->I,ii->J,in.A*ii->A%M,(in.B+in.A*ii->B)%M};
}
if(l==r)return;
// write(l,r,num);
LL mid=l+r>>1LL;
if(x>mid)ins(in,x,mid+1,r,num<<1LL|1LL);
else ins(in,x,l,mid,num<<1LL);
}
void query(LL L,LL R,LL x,LL l,LL r,LL num){
if(L<=l&&r<=R){
vector<MODIFY>::iterator ii;
ii=lower_bound(T[num].begin(),T[num].end(),(MODIFY){0LL,x,0LL,0LL},cmp2);
qA=ii->A*qA%M;qB=(ii->B+ii->A*qB)%M;
return;
}
LL mid=l+r>>1LL;
if(L<=mid)query(L,R,x,l,mid,num<<1LL);
if(R>mid)query(L,R,x,mid+1LL,r,num<<1LL|1LL);
}
int main(){
freopen("r.in","r",stdin);
freopen("w.out","w",stdout);
LL flg,o,Q,i,j,x,y;
scanf("%lld%lld%lld",&flg,&n,&M);flg&=1;
rep(i,1,n)scanf("%lld",&w[i]);
scanf("%lld",&Q);mx=min(100000LL,Q);
mdf0=(MODIFY){1LL,n,1LL,0LL};sb=(MODIFY){n+1,n+1,0LL,0LL};
build(1LL,mx,1LL);
while(Q--){
scanf("%lld%lld%lld%lld",&o,&i,&j,&x);
if(flg)i^=ans,j^=ans;
if(o==1){
scanf("%lld",&y);
ins((MODIFY){i,j,x,y},++m,1LL,mx,1LL);
}
else{
qA=1;qB=0;if(flg)x^=ans;
query(i,j,x,1LL,mx,1LL);
printf("%lld\n",ans=(qA*w[x]+qB)%M);
}
}
write(1,mx,1);
return 0;
}
到现在才知道这题的思路用多恐怖。
实际上
这题是修改log，查询log^2的。
虽然这题要求强制在线，但是
相当于
离线。由于每次的query只会对已修改的操作，所以可以
分步进行预处理
。每次对一个l==r的节点x修改，然后对包含它的节点进行线段树合并，当且仅当这个节点的r恰好为x的r（或l）。
然后查询时使用二分查找。
最后注意对STL say goodbye！！！
AC代码：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
using namespace std;
#define rep(i,j,k) for(i=j;i<=k;++i)
#define per(i,j,k) for(i=j;i>=k;--i)
#define LL long long
#define pll pair<LL,LL>
#define mkp make_pair
#define X first
#define Y second
LL n,M,m,w[100000],mx,ans;
struct MODIFY{LL I,J,A,B;}mdf,qj[7000000];
pll T[400000];LL id;
LL L,R,wz,qA,qB;
void ins(LL l,LL r,LL num){
if(l==r){
LL l0=id+1;
if(mdf.I>1)qj[++id]=(MODIFY){1,mdf.I-1,1,0};
qj[++id]=mdf;
if(mdf.J<n)qj[++id]=(MODIFY){mdf.J+1,n,1,0};
T[num]=mkp(l0,id);return;
}
LL mid=l+r>>1;
if(m>mid)ins(mid+1,r,num<<1|1);
else ins(l,mid,num<<1);
if(m==r){
LL l0=id+1,k=1,l1=T[num<<1].X,l2=T[num<<1|1].X;
while(k<=n){
if(qj[l1].J<qj[l2].J){
qj[++id]=(MODIFY){k,qj[l1].J,qj[l1].A*qj[l2].A%M,(qj[l1].B*qj[l2].A+qj[l2].B)%M};
k=qj[l1].J+1;++l1;
}
else if(qj[l1].J>qj[l2].J){
qj[++id]=(MODIFY){k,qj[l2].J,qj[l1].A*qj[l2].A%M,(qj[l1].B*qj[l2].A+qj[l2].B)%M};
k=qj[l2].J+1;++l2;
}
else{
qj[++id]=(MODIFY){k,qj[l1].J,qj[l1].A*qj[l2].A%M,(qj[l1].B*qj[l2].A+qj[l2].B)%M};
k=qj[l1].J+1;++l1;++l2;
}
}
T[num]=mkp(l0,id);
}
}
bool cmp(MODIFY u,MODIFY v){
return u.J<v.J;
}
void query(LL l,LL r,LL num){
if(L<=l&&r<=R){
int tmp=lower_bound(qj+T[num].X,qj+T[num].Y+1,(MODIFY){0LL,wz,0LL,0LL},cmp)-qj;
qA=qj[tmp].A*qA%M;qB=(qj[tmp].A*qB+qj[tmp].B)%M;
return;
}
int mid=l+r>>1;
if(L<=mid)query(l,mid,num<<1);
if(R>mid)query(mid+1,r,num<<1|1);
}
int main(){
LL flg,i,Q,o,j,x,y;
scanf("%lld%lld%lld",&flg,&n,&M);flg&=1;
rep(i,1,n)scanf("%lld",&w[i]);
scanf("%lld",&Q);mx=min(100000LL,Q);
while(Q--){
scanf("%lld%lld%lld%lld",&o,&i,&j,&x);
if(flg)i^=ans,j^=ans;
if(o==1){
scanf("%lld",&y);
mdf=(MODIFY){i,j,x,y};++m;
ins(1LL,mx,1LL);
}
else{
qA=1;qB=0;L=i;R=j;wz=x;if(flg)wz^=ans;
query(1LL,mx,1LL);
printf("%lld\n",ans=(qA*w[wz]+qB)%M);
}
}
return 0;
}
转载请注明原文地址: https://www.6miu.com/read-39898.html
