jzoj 6078.【GDOI2019模拟2019.3.22】魔法阵 树状数组套线段树+set
Description
Input
Output
Sample Input
5 3
3 3 3 3 3
5 3 1 3 5
0 2 5
0 2 7
1 3 3
Sample Output
135
135
405
Data Constraint
分析:
显然是单调增的。因为只能改大,对于修改,相当于把从后面小于的都改成。
显然是每一个数一段一段这样的,修改相当于把一个区间改成相同的一段,可以用set维护。
对于一段相同的,假设全为,区间为。相当于把b中小于等于的求积,并求出小于的数的个数。因为总个数已知,小于的可以使用树状数组套权值线段树求出,大于的直接快速幂。
修改就直接修改树状数组即可。
代码:
#include <iostream>
#include <cstdio>
#include <cmath>
#include <set>
#define LL long long
const int maxn=1e5+7;
const int maxa=1e9;
const LL mod=1e9+7;
using namespace std;
int n,T,cnt,op,x,y;
int a[maxn],b[maxn],root[maxn];
LL ans;
struct typ{
int data,r;
};
bool operator <(typ a,typ b)
{
if (a.r==b.r) return a.data<b.data;
return a.r<b.r;
}
set <typ> s;
struct rec{
int x;
LL y;
};
struct node{
int l,r;
rec data;
}t[maxn*400];
LL ksm(LL x,LL y)
{
if (y==0) return 1;
LL c=ksm(x,y/2);
c=c*c%mod;
if (y&1) c=c*x%mod;
return c;
}
rec merge(rec a,rec b)
{
return (rec){a.x+b.x,a.y*b.y%mod};
}
void ins(int &p,int l,int r,int x,int k)
{
if (!p)
{
p=++cnt;
t[p].data=(rec){0,1};
}
if (l==r)
{
t[p].data.x+=k;
if (k==1) t[p].data.y=t[p].data.y*(LL)x%mod;
else
{
LL inv=ksm((LL)x,mod-2);
t[p].data.y=t[p].data.y*inv%mod;
}
return;
}
int mid=(l+r)/2;
if (x<=mid) ins(t[p].l,l,mid,x,k);
else ins(t[p].r,mid+1,r,x,k);
t[p].data=merge(t[t[p].l].data,t[t[p].r].data);
}
rec query(int p,int l,int r,int x,int y)
{
if (!p) return t[p].data;
if ((l==x) && (r==y)) return t[p].data;
int mid=(l+r)/2;
if (y<=mid) return query(t[p].l,l,mid,x,y);
else if (x>mid) return query(t[p].r,mid+1,r,x,y);
else return merge(query(t[p].l,l,mid,x,mid),query(t[p].r,mid+1,r,mid+1,y));
}
void updata(int x,int y,int op)
{
for (int i=x;i<=n;i+=i&(-i)) ins(root[i],1,maxa,y,op);
}
rec getsum(int x,int k)
{
rec sum=(rec){0,1};
for (int i=x;i>0;i-=i&(-i)) sum=merge(sum,query(root[i],1,maxa,1,k));
return sum;
}
LL getans(int l,int r,int k)
{
rec ans1=getsum(r,k),ans2=getsum(l-1,k);
rec d=(rec){ans1.x-ans2.x,ans1.y*ksm(ans2.y,mod-2)%mod};
int len=r-l+1;
return ksm(k,(LL)len-(LL)d.x)*d.y%mod;
}
int main()
{
freopen("magic.in","r",stdin);
freopen("magic.out","w",stdout);
scanf("%d%d",&n,&T);
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
for (int i=1;i<=n;i++) scanf("%d",&b[i]);
int maxx=a[1];
ans=1,t[0].data.y=1;
for (int i=1;i<=n;i++)
{
if (a[i]>maxx)
{
s.insert((typ){maxx,i-1});
maxx=a[i];
}
ans=ans*(LL)min(maxx,b[i])%mod;
updata(i,b[i],1);
}
s.insert((typ){maxx,n});
for (int i=1;i<=T;i++)
{
scanf("%d%d%d",&op,&x,&y);
if (op==0)
{
set <typ>::iterator it=s.lower_bound((typ){0,x}),it0;
int l,last=x;
if (it==s.begin()) l=1;
else
{
it--;
l=(*it).r+1;
it++;
}
while (it!=s.end())
{
int r=(*it).r,num=(*it).data;
if (num>y) break;
ans=ans*ksm(getans(last,r,num),mod-2)%mod;
it0=it;
it++;
s.erase(it0);
if (last!=l) s.insert((typ){num,last-1});
l=last=r+1;
}
if (last>x)
{
s.insert((typ){y,last-1});
ans=ans*getans(x,last-1,y)%mod;
}
}
else
{
set <typ>::iterator it=s.lower_bound((typ){0,x});
int num=(*it).data;
updata(x,b[x],-1);
ans=ans*ksm((LL)min(b[x],num),mod-2)%mod;
b[x]=y;
updata(x,b[x],1);
ans=ans*(LL)min(b[x],num)%mod;
}
printf("%lld\n",ans);
}
}