BZOJ 2161 布娃娃 (主席树)

想了一个主席树做法

我们把每个区间的两个端点拆开

对$L,R$分别从小到大排序，分别从左到右依次把对应标号的$c_{i}$插入到权值主席树里

每次查询$p_{i}$，在排序后的$L,R$数组上分别二分找到第一个小于等于$p_{i}$的位置

那么$L,R$的主席树相减之后就是能对$p_{i}$产生贡献的区间

在主席树上二分即可

似乎平衡树和线段树的做法空间比我优秀得多..

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #define N1 100010

 #define M1 8000100

 using namespace std;

 const int mod=;

 struct SEG{

 int root1[N1],root2[N1],ls[M1],rs[M1],sz[M1],tot;

 inline void pushup(int rt){ sz[rt]=sz[ls[rt]]+sz[rs[rt]]; }

 void update(int x,int l,int r,int r1,int &r2)

 {

     if((!r2)||(r1==r2)){ r2=++tot; sz[r2]=sz[r1]; ls[r2]=ls[r1]; rs[r2]=rs[r1]; }

     if(l==r){ sz[r2]++; return; }

     int mid=(l+r)>>;

     if(x<=mid) update(x,l,mid,ls[r1],ls[r2]);

     else update(x,mid+,r,rs[r1],rs[r2]);

     pushup(r2);

 }

 int query(int K,int l,int r,int r1,int r2)

 {

     if(K>sz[r1]-sz[r2]) return ;

     if(l==r) return l;

     int mid=(l+r)>>;

     if(K>sz[rs[r1]]-sz[rs[r2]])

         return query(K-sz[rs[r1]]+sz[rs[r2]],l,mid,ls[r1],ls[r2]);

     else return query(K,mid+,r,rs[r1],rs[r2]);

 }

 }s;

 int n,mx;

 int P[N1],C[N1];

 struct node{int id,x;}L[N1],R[N1];

 int cmp(node s1,node s2){ return s1.x<s2.x; }

 void make()

 {

     int Padd, Pfirst, Pmod, Pprod, Cadd, Cfirst, Cmod, Cprod, Ladd, Lfirst, Lmod, Lprod, Radd, Rfirst, Rmod, Rprod, i;

     scanf("%d%d%d%d%d%d%d%d%d%d%d%d%d%d%d%d",&Padd, &Pfirst, &Pmod, &Pprod, &Cadd, &Cfirst, &Cmod, &Cprod, &Ladd, &Lfirst, &Lmod, &Lprod, &Radd, &Rfirst, &Rmod, &Rprod);

     P[]=Pfirst%Pmod; for(i=;i<=n;i++) P[i]=(1ll*P[i-]*Pprod+Padd+i)%Pmod;

     C[]=Cfirst%Cmod; for(i=;i<=n;i++) C[i]=(1ll*C[i-]*Cprod+Cadd+i)%Cmod, mx=max(mx,C[i]); mx=max(mx,C[]);

     L[].x=Lfirst%Lmod; for(i=;i<=n;i++) L[i].x=(1ll*L[i-].x*Lprod+Ladd+i)%Lmod;

     R[].x=Rfirst%Rmod; for(i=;i<=n;i++) R[i].x=(1ll*R[i-].x*Rprod+Radd+i)%Rmod;

     for(i=;i<=n;i++){ L[i].id=i, R[i].id=i; if(L[i].x>R[i].x) swap(L[i].x,R[i].x); }

     sort(L+,L+n+,cmp); sort(R+,R+n+,cmp);

     for(i=;i<=n;i++) s.update(C[L[i].id],,mx,s.root1[i-],s.root1[i]);

     for(i=;i<=n;i++) s.update(C[R[i].id],,mx,s.root2[i-],s.root2[i]);

 }

 int ans[N1];

 int main()

 {

     scanf("%d",&n);

     make();

     int i,j,l,r,mid,xl,xr,ret=;

     for(i=;i<=n;i++)

     {

         if(P[i]<L[].x||P[i]>R[n].x) continue;

         l=,r=n,xl=;

         while(l<=r)

         {

             mid=(l+r)>>;

             if(L[mid].x<=P[i]) xl=mid,l=mid+;

             else r=mid-;

         }

         l=,r=n,xr=;

         while(l<=r)

         {

             mid=(l+r)>>;

             if(R[mid].x<=P[i]-) xr=mid,l=mid+;

             else r=mid-;

         }

         ans[i]=s.query(i,,mx,s.root1[xl],s.root2[xr]);

         (ret+=ans[i])%=mod;

     }

     printf("%d\n",ret);

     return ;

 }

巴特西

BZOJ 2161 布娃娃 (主席树)

最新文章

热门文章