C54 可持久化线段树+前缀和+二分 P2468 [SDOI2010] 粟粟的书架

#include <bits/stdc++.h>
using namespace std;

int read(){ //快读
  int x=0;char c=getchar();
  while(c<'0'||c>'9')c=getchar();
  while(c>='0'&&c<='9')x=x*10+c-48,c=getchar();
  return x;
}
const int N=500005;
#define mid ((l+r)>>1)
int n,m,q;
int a[ 205][ 205],f[ 205][ 205][ 1005],g[ 205][ 205][ 1005];
//f[ i][ j][ k]:区间[ (1,1),(i,j)]内>=k页的书的总页数
//g[ i][ j][ k]:区间[ (1,1),(i,j)]内>=k页的书的总个数
int getsum(int x1,int y1,int x2,int y2,int k,int t){ //返回区间和
  if(t) return f[ x2][ y2][ k]-f[ x2][ y1-1][ k]-f[ x1-1][ y2][ k]+f[ x1-1][ y1-1][ k];
  else  return g[ x2][ y2][ k]-g[ x2][ y1-1][ k]-g[ x1-1][ y2][ k]+g[ x1-1][ y1-1][ k];
}
void work1(){ //条件前缀和+二分
  int mx=-1e9;
  for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
      a[ i][ j]=read(),mx=max(mx,a[ i][ j]);
  for(int k=1;k<=mx;k++)
    for(int i=1;i<=n;i++)
      for(int j=1;j<=m;j++){
        f[ i][ j][ k]=f[ i-1][ j][ k]+f[ i][ j-1][ k]-f[ i-1][ j-1][ k]+(a[ i][ j]>=k)*a[ i][ j];
        g[ i][ j][ k]=g[ i-1][ j][ k]+g[ i][ j-1][ k]-g[ i-1][ j-1][ k]+(a[ i][ j]>=k);
      }
  for(int i=1;i<=q;i++){
    int x1=read(),y1=read(),x2=read(),y2=read(),h=read();
    if(getsum(x1,y1,x2,y2,1,1)<h){puts("Poor QLW");continue;}
    int l=0,r=mx+1; //二分书页范围[ 1,mx]
    while(l+1<r) getsum(x1,y1,x2,y2,mid,1)>=h?l=mid:r=mid;
    printf("%d\n",getsum(x1,y1,x2,y2,l,1)-(getsum(x1,y1,x2,y2,l,0)-h)/l);
  }    
}

int b[ N],root[ N],tot; //root根节点,tot节点个数
int ls[ N*25],rs[ N*25],sum[ N*25],siz[ N*25];
//sum:区间内书的总页数
//siz:区间内书的总个数
void change(int &u,int v,int l,int r,int x){ //点修
  u=++tot; //动态开点
  ls[u]=ls[v];rs[u]=rs[v];sum[u]=sum[v]+x;siz[u]=siz[v]+1;
  if(l==r)return;   //二分书页范围[ 1,mx]
  if(x<=mid)change(ls[u],ls[v],l,mid,x);
  else change(rs[u],rs[v],mid+1,r,x);
}
int query(int u,int v,int l,int r,int h){ //点查
  if(l==r)return (h+l-1)/l;
  int s=sum[ rs[u]]-sum[ rs[v]];  //二分书页范围[ 1,mx]
  if(h<=s)return query(rs[u],rs[v],mid+1,r,h);
  else return query(ls[u],ls[v],l,mid,h-s)+siz[ rs[u]]-siz[ rs[v]];
}
void work2(){ //可持久化线段树
  int mx=-1e9;
  for(int i=1;i<=m;i++)b[ i]=read(),mx=max(mx,b[ i]);
  for(int i=1;i<=m;i++)change(root[ i],root[ i-1],1,mx,b[ i]);
  for(int i=1,y1,y2,h;i<=q;i++){
    read(),y1=root[ read()-1],read(),y2=root[ read()],h=read();
    if(sum[ y2]-sum[ y1]<h){puts("Poor QLW");continue;}
    printf("%d\n",query(y2,y1,1,mx,h));
  }
}
int main(){
  n=read(),m=read(),q=read(); //n行,m列,q次查询
  if(n>1) work1(); //条件前缀和+二分
  else work2();    //可持久化线段树
}

C54 可持久化线段树+前缀和+二分 P2468 [SDOI2010] 粟粟的书架

#include <bits/stdc++.h>
using namespace std;

int read(){ //快读 int x=0;char c=getchar(); while(c<'0'||c>'9')c=getchar(); while(c>='0'&&c<='9')x=x*10+c-48,c=getchar(); return x; } const int N=500005; #define mid ((l+r)>>1) int n,m,q; int a[ 205][ 205],f[ 205][ 205][ 1005],g[ 205][ 205][ 1005]; //f[ i][ j][ k]:区间[ (1,1),(i,j)]内>=k页的书的总页数 //g[ i][ j][ k]:区间[ (1,1),(i,j)]内>=k页的书的总个数 int getsum(int x1,int y1,int x2,int y2,int k,int t){ //返回区间和 if(t) return f[ x2][ y2][ k]-f[ x2][ y1-1][ k]-f[ x1-1][ y2][ k]+f[ x1-1][ y1-1][ k]; else return g[ x2][ y2][ k]-g[ x2][ y1-1][ k]-g[ x1-1][ y2][ k]+g[ x1-1][ y1-1][ k]; } void work1(){ //条件前缀和+二分 int mx=-1e9; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) a[ i][ j]=read(),mx=max(mx,a[ i][ j]); for(int k=1;k<=mx;k++) for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ f[ i][ j][ k]=f[ i-1][ j][ k]+f[ i][ j-1][ k]-f[ i-1][ j-1][ k]+(a[ i][ j]>=k)*a[ i][ j]; g[ i][ j][ k]=g[ i-1][ j][ k]+g[ i][ j-1][ k]-g[ i-1][ j-1][ k]+(a[ i][ j]>=k); } for(int i=1;i<=q;i++){ int x1=read(),y1=read(),x2=read(),y2=read(),h=read(); if(getsum(x1,y1,x2,y2,1,1)<h){puts("Poor QLW");continue;} int l=0,r=mx+1; //二分书页范围[ 1,mx] while(l+1<r) getsum(x1,y1,x2,y2,mid,1)>=h?l=mid:r=mid; printf("%d\n",getsum(x1,y1,x2,y2,l,0)-(getsum(x1,y1,x2,y2,l,1)-h)/l); }
}

int b[ N],root[ N],tot; //root根节点,tot节点个数 int ls[ N25],rs[ N25],sum[ N25],siz[ N25]; //sum:区间内书的总页数 //siz:区间内书的总个数 void change(int &u,int v,int l,int r,int x){ //点修 u=++tot; //动态开点 ls[ u]=ls[ v];rs[ u]=rs[ v];sum[ u]=sum[ v]+x;siz[ u]=siz[ v]+1; if(lr)return; //二分书页范围[ 1,mx] if(x<=mid)change(ls[ u],ls[ u],l,mid,x); else change(rs[ u],rs[ u],mid+1,r,x); } int query(int u,int v,int l,int r,int h){ //点查 if(lr)return (h+l-1)/l; int s=sum[ rs[ u]]-sum[ rs[ v]]; //二分书页范围[ 1,mx] if(h<=s)return query(rs[ u],rs[ v],mid+1,r,h); else return query(ls[ u],ls[ v],l,mid,h-s)+siz[ rs[ u]]-siz[ rs[ v]]; } void work2(){ //可持久化线段树 int mx=-1e9; for(int i=1;i<=m;i++)b[ i]=read(),mx=max(mx,b[ i]); for(int i=1;i<=m;i++)change(root[ i],root[ i-1],1,mx,b[ i]); for(int i=1,y1,y2,h;i<=q;i++){ read(),y1=root[ read()-1],read(),y2=root[ read()],h=read(); if(sum[ y2]-sum[ y1]<h){puts("Poor QLW");continue;} printf("%d\n",query(y2,y1,1,mx,h)); } } int main(){ n=read(),m=read(),q=read(); //n行,m列,q次查询 if(n>1) work1(); //条件前缀和+二分 else work2(); //可持久化线段树 }</pre>