发现lca的倍增解法和st表差不多。。原理都是一样的
/* 整篇文章分成两部分，中间没有图片的部分，中间有图片的部分 分别用ST表求f1,f2表示以第i个单词开始，连续1<<j行能写多少单词 */ #include<bits/stdc++.h> #define FIN freopen("in.txt","r",stdin); using namespace std; #define ll long long #define MX 100005 #define inf 0x3f3f3f3f int mx,n,w,dw,pw,a[MX]; int f1[MX][30],f2[MX][30]; void ST(){ for(int i=1;i<=n;i++){//只填一行的状态 int cnt=a[i],j=i+1; while(cnt+a[j]+1<=w && j<=n) cnt+=a[j++]+1; f1[i][0]=j-i; } for(int j=1;(1<<j)<=mx;j++) for(int i=1;i<=n;i++) f1[i][j]=f1[i][j-1]+f1[i+f1[i][j-1]][j-1]; for(int i=1;i<=n;i++){ int cnt=0,j=i,flag=0; while(cnt+a[j]+flag<=dw)//图片的左端能填入的单词 cnt+=a[j++]+flag,flag=1;//填入第一个单词后下一个单词就要空一格了 int k=j; cnt=flag=0; while(cnt+a[k]+flag<=w-pw-dw)//图片右端能填入的单词 cnt+=a[k++]+flag,flag=1; f2[i][0]=k-i; } for(int j=1;(1<<j)<=mx;j++) for(int i=1;i<=n;i++) if(f2[i][j-1]==0) f2[i][j]=0;//第i个单词无法填入有图片的行 else f2[i][j]=f2[i][j-1]+f2[i+f2[i][j-1]][j-1]; } int RMQ1(int i,int x){//i是当前填的单词下标，x是可以填的行数，返回当前填到了第几个单词 if(x==0) return i; while(x && i<=n){ int j=0; while((1<<(j+1))<=x)j++;//先求出最大的j i+=f1[i][j]; x-=(1<<j); } return i; } int RMQ2(int i,int x){ if(x==0) return i; while(x && i<=n){ int j=0; while((1<<(j+1))<=x) j++; i+=f2[i][j];x-=(1<<j); } return i; } int RMQ3(int i){//返回填i-n个单词需要的行数 int ret=0; while(i<=n){ int j=0; while(i+f1[i][j+1]<=n) j++;//找到最大的j i+=f1[i][j]; ret+=(1<<j); } return ret; } struct Query{ int x,h; }q[MX]; int main(){ int T,m; cin >> T; while(T--){ scanf("%d%d%d%d",&n,&w,&pw,&dw); for(int i=1;i<=n;i++) scanf("%d",&a[i]); scanf("%d",&m); mx=n; for(int i=1;i<=m;i++) { scanf("%d%d",&q[i].x,&q[i].h); mx=max(mx,n+q[i].x+q[i].h); } ST(); for(int i=1;i<=m;i++){ int x=q[i].x,h=q[i].h; int tmp=RMQ3(1);//只用f1 if(tmp<=x-1){ printf("%d ",tmp+h); continue; } int ans=x+h-1; int p=RMQ1(1,x-1);//从第一个单词开始连续x-1行能填的单词书 p=RMQ2(p,h);//从第p个单词开始连续h行能填的单词数 if (p<=n) ans+=RMQ3(p);//把剩下的单词填进去 printf("%d ",ans); } } return 0; }