#46. [청화합숙훈련 2014] 현학
6061 단어 UOJ
5점 코드부터 끊어.
#include
#include
#include
#include
#include
#include
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
#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;
vectorT[7000000];
LL qA,qB;
void write(LL l,LL r,LL num){
printf("%lld: ",num);
vector::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>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::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.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::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
",ans=(qA*w[x]+qB)%M);
}
}
write(1,mx,1);
return 0;
} 이제야 이 문제의 사고방식이 얼마나 무서운지 알게 되었다.
실상
이 문제는 로그를 수정하고 로그^2를 조회하는 것입니다.
이 문제는 강제 온라인을 요구하지만,
... 에 상당하다
오프라인 상태입니다.매번query는 수정된 작업만 할 수 있기 때문에
단계별 사전 처리
.매번 l==r의 노드 x를 수정한 다음에 그 노드를 포함하는 노드를 라인 트리로 합쳐서 이 노드의 r가 x의 r(또는 l)일 때만 합친다.
그리고 조회할 때 2분 검색을 사용합니다.
마지막으로 STL say goodbye에 주목!!!
AC 코드:
#include
#include
#include
#include
#include
#include
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
#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>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].Jqj[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>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
",ans=(qA*w[wz]+qB)%M);
}
}
return 0;
} 좋은 웹페이지 즐겨찾기
