BZOJ 1798 1798: [Ahoi2009]Seq 維護序列seq
題目概述:
區間操作題。能支援區間加值，區間乘值，詢問區間總和。
思路:
這題我是先用線段樹來實作。
也附上treap版，但常數較大。
需要思考的是下放標記的方式。
下放加法就直接下放。
下放乘法應該要將子樹的add,mul都乘上。
這邊大概說明一下就是:
( a*b + c ) * d = a*b*d + c*d
然後要注意的是mul初始值應該要為1，若設為0會很麻煩的。
AC code:
//By SCJ
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
int n,p;
typedef long long ll;
struct Node{
ll sum,add,mul;
Node()
{
add=0;mul=1;
}
}seg[600005];
inline ll all(int l,int r,int i)
{
ll res=seg[i].sum%p;
res*=(seg[i].mul%p);
res%=p;
return (res+seg[i].add*((r-l+1)%p)%p)%p;
}
inline void up(int l,int r,int i)
{
int mid=(l+r)/2;
seg[i].sum=(all(l,mid,i*2)+all(mid+1,r,i*2+1))%p;
}
inline void down(int l,int r,int i)
{
seg[i].sum=all(l,r,i);
ll ta=seg[i].mul,tb=seg[i].add;
seg[i*2].mul=seg[i*2].mul*ta%p;
seg[i*2+1].mul=seg[i*2+1].mul*ta%p;
seg[i*2].add=(seg[i*2].add*ta%p + tb%p )%p;
seg[i*2+1].add=(seg[i*2+1].add*ta%p + tb%p )%p;
seg[i].add=0;
seg[i].mul=1;
}
inline void build(int l,int r,int i)
{
if(l==r)
{
int tp;//cin>>tp;
scanf("%d",&tp);
seg[i].sum=tp;
return ;
}
int mid=(l+r)>>1;
build(l,mid,i*2);
build(mid+1,r,i*2+1);
up(l,r,i);
}
inline void update(int l,int r,int i,int ql,int qr,int c,int type)
{
if(r<ql||l>qr) return ;
down(l,r,i);
if(l>=ql&&r<=qr)
{
if(type==1) seg[i].mul=c;
else seg[i].add=c;
return ;
}
int mid=(l+r)/2;
update(l,mid,i*2,ql,qr,c,type);
update(mid+1,r,i*2+1,ql,qr,c,type);
up(l,r,i);
}
inline int query(int l,int r,int i,int ql,int qr)
{
if(r<ql||l>qr) return 0;
down(l,r,i);
if(l>=ql&&r<=qr) return all(l,r,i)%p;
int mid=(l+r)>>1;
return (query(l,mid,i*2,ql,qr)+query(mid+1,r,i*2+1,ql,qr))%p;
}
main()
{
scanf("%d%d",&n,&p);
build(1,n,1);
int q;
scanf("%d",&q);
while(q--)
{
int type,a,b,c;//cin>>type;
scanf("%d",&type);
if(type==3)
{
scanf("%d%d",&a,&b);
printf("%d\n",query(1,n,1,a,b));
}
else
{
scanf("%d%d%d",&a,&b,&c);
update(1,n,1,a,b,c,type);
}
}
}
常數較大的treap版:
//By SCJ
#include<bits/stdc++.h>
//#include<random>
using namespace std;
#define endl '\n'
typedef long long ll;
struct treap;
treap *nul;
int n,p;
struct treap{
ll val,sum,add,mul,sz,pr,pri;
treap *l,*r;
treap(int _val)
{
val=sum=_val;
add=0;
sz=mul=1;
l=r=nul;
pri=rand();
}
int all()
{
return ((sum*mul%p)+add*sz%p)%p;
}
void up()
{
sum=l->all()+r->all()+val;
sz=l->sz+r->sz+1;
}
void down()
{
mul%=p;add%=p;
sum=all();
val=(val*mul%p+add)%p;
l->mul=l->mul*mul%p;
l->add=(l->add*mul%p + add )%p;
r->mul=r->mul*mul%p;
r->add=(r->add*mul%p + add )%p;
add=0;mul=1;
}
};
//mt19937 mt(56);
treap *merge(treap *a,treap *b)
{
if(a==nul) return b;
if(b==nul) return a;
// if(rd()%(a->sz+b->sz)<=a->sz){
if(a->pri<b->pri){
a->down();
a->r=merge(a->r,b);
a->up();
return a;
}
else{
b->down();
b->l=merge(a,b->l);
b->up();
return b;
}
}
void split(treap *t,treap *&a,treap *&b,int k)
{
if(t==nul) {a=b=nul;return ;}
t->down();
int asz=t->l->sz+1;
if(asz<=k){
a=t;
split(t->r,a->r,b,k-asz);
}
else{
b=t;
split(t->l,a,b->l,k);
}
t->up();
}
int main()
{
srand(12);
nul=new treap(0);nul->sz=0;
treap *root=nul;
scanf("%d%d",&n,&p);
for(int i=1;i<=n;++i)
{
int tp;
scanf("%d",&tp);
root=merge(root,new treap(tp));
}
int q;
scanf("%d",&q);
while(q--)
{
treap *tl=nul,*tr=nul;
int type,a,b,c;
scanf("%d",&type);
if(type==1)
{
scanf("%d%d%d",&a,&b,&c);
split(root,tl,root,a-1);
split(root,root,tr,b-a+1);
root->mul=root->mul*c%p;
root->add=root->add*c%p;
root=merge(merge(tl,root),tr);
}
else if(type==2)
{
scanf("%d%d%d",&a,&b,&c);
split(root,tl,root,a-1);
split(root,root,tr,b-a+1);
root->add=(root->add+c)%p;
root=merge(merge(tl,root),tr);
}
else
{
scanf("%d%d",&a,&b);
split(root,tl,root,a-1);
split(root,root,tr,b-a+1);
printf("%d\n",root->all());
root=merge(merge(tl,root),tr);
}
}
}
沒有留言:
張貼留言