单调队列 TLE

二进制拆分 AC，最慢点 1秒多

loj上都能过，但也是二进制拆分快。

代码，注释掉的是单调队列：

#include<bits/stdc++.h>
using namespace std;
const int N=1003,B=63,P=1e8+7;
int n,m,o,c[N],v[N],t[N],bl[N],bg[16],q[N],w[N];
struct A{
	int f[N];
	void add(int c,int v){
		for(int i=m;i>=c;--i)f[i]=max(f[i],f[i-c]+v);
	}
	void add(int x){
		int c=::c[x],v=::v[x],t=::t[x],i;
		for(i=1;i<=t;i*=2)add(c*i,v*i),t-=i;
		add(c*t,v*t);
	/*	int c=::c[x],v=::v[x],t=::t[x],i,j,k,u,l,r;
		for(i=0;i<c;++i){
			l=1,q[r=1]=i,w[1]=f[i];
			for(j=i+c,k=1;j<=m;j+=c,++k){
				if((j-q[l])/c>t)++l;
				u=f[j]-k*v,f[j]=max(f[j],w[l]+k*v);
				while(l<=r&&w[r]<u)--r;
				w[++r]=u,q[r]=j;
			}
		}*/
	}
}a[16][N],now;
int main(){ios::sync_with_stdio(0);cin.tie(0);
	int T,i,j,l,r,la;
	for(cin>>T;T--;){
		cin>>n>>m>>o,la=0;
		for(i=1;i<=n;++i)cin>>c[i];
		for(i=1;i<=n;++i)cin>>v[i];
		for(i=1;i<=n;++i)cin>>t[i];
		for(l=1,i=0;l<=n;++i,l+=B){
			bg[i]=l;
			for(j=l;j<l+B&&j<=n;++j)bl[j]=i;
			a[i][n]=i?a[i-1][n]:a[i][0];
			if(i)for(j=l-B;j<l;++j)a[i][n].add(j);
			for(j=n;j>l;--j)a[i][j-1]=a[i][j],a[i][j-1].add(j);
		}
		while(o--){
			cin>>i>>j,i=(i+la-1)%n+1,j=(j+la-1)%n+1,l=min(i,j),r=max(i,j),now=a[bl[l]][r];
			for(i=bg[bl[l]];i<l;++i)now.add(i);
			for(i=1,la=j=0;i<=m;++i)la=(la+now.f[i])%P,j^=now.f[i];
			cout<<la<<' '<<j<<'\n';
		}
	}
}