这题不知道为什么就是T，简直有毒。
思想和巴比伦那题差不多。
话说，寻找一个区间内满足一个条件的最左（右）边的一个数，用线段树来写，应该是可以的，之前博客里大连网赛那题的线段树写法应该是有点小问题的。现在按照下面的套路来，虽然是T的= =。当然也可以用单调栈来实现。
代码如下（T的）：
#include <stdio.h>
#include <algorithm>
#include <string.h>
#define ls (o<<1)
#define rs (o<<1|1)
#define t_mid (l+r>>1)
#define lson ls,l,t_mid
#define rson rs,t_mid+1,r
using namespace std;
typedef long long ll;
const int N = + ; int n,m,q;
ll atk[N];
int nxt[N],pos[N];
int c[N<<],d[N<<];
// 线段树维护(nxt[i] - i + 1)的最大值和(nxt[i])的最大值 void build(int o,int l,int r)
{
if(l == r) {c[o] = nxt[l]-l+; d[o] = nxt[l]; return;}
build(lson);
build(rson);
c[o] = max(c[ls],c[rs]); d[o] = max(d[ls],d[rs]);
} int Find(int o,int l,int r,int ql,int qr,int where)
{
//if(ql > qr) return -1;
if(l == r)
{
if(nxt[l] >= where) return l;
else return -;
}
int ans = -;
if(t_mid >= qr)
{
if(d[ls] >= where) ans = Find(lson,ql,qr,where);
}
else if(ql > t_mid)
{
if(d[rs] >= where) ans = Find(rson,ql,qr,where);
}
else
{
if(d[ls] >= where) ans = Find(lson,ql,t_mid,where);
if(ans == - && d[rs] >= where) ans = Find(rson,t_mid+,qr,where);
}
return ans;
} int Find2(int o,int l,int r,int ql,int qr)
{
if(ql == l && qr == r)
{
return d[o];
}
int ans = ;
if(t_mid >= qr) ans = Find2(lson,ql,qr);
else if(t_mid < ql) ans = Find2(rson,ql,qr);
else
{
ans = max(Find2(lson,ql,t_mid), Find2(rson,t_mid+,qr));
} return ans;
} int query(int o,int l,int r,int ql,int qr)
{
if(ql == l && qr == r)
{
return c[o];
}
if(qr <= t_mid) return query(lson,ql,qr);
else if(ql > t_mid) return query(rson,ql,qr);
else return max(query(lson,ql,t_mid), query(rson,t_mid+,qr));
} int solve(int ql,int qr)
{
int temp = -;
//int temp = Find(1,1,n,ql,qr,qr); int ans = , ans2 = , ans3 = ; if(temp == -) ans2 = query(,,n,ql,qr);
else
{
ans = qr - temp + ;
if(temp != ql) ans2 = query(,,n,ql,temp-);
}
if(ql > )
{
ans3 = Find2(,,n,,ql-);
if(ans3 > qr) ans3 = qr;
if(ans3 >= ql) ans3 = ans3 - ql + ;
} return max(max(max(ans,ans2),ans3),);
} int main()
{
int T;scanf("%d",&T);
while(T--)
{
memset(nxt,-,sizeof(nxt));
//memset(atk,0,sizeof(atk));
scanf("%d%d%d",&n,&m,&q);
//nxt[0] = n;
for(int i=;i<=n;i++) {scanf("%d",atk+i);atk[i]+=atk[i-];}
for(int i=;i<=m;i++) scanf("%d",pos+i);
for(int i=;i<=m;i++)
{
int hp;scanf("%d",&hp);
int now = pos[i] - ;
int l = pos[i], r = n, ans = -;
while(l <= r)
{
int mid = l + r >> ;
if(atk[mid] - atk[now] <= hp) {ans = mid; l = mid + ;}
else r = mid - ;
}
nxt[pos[i]] = max(ans,nxt[pos[i]]); ans = -;
l = , r = pos[i];
now = pos[i];
while(l <= r)
{
int mid = l + r >> ;
if(atk[now] - atk[mid-] <= hp) {ans = mid; r = mid - ;}
else l = mid + ;
}
nxt[ans] = max(pos[i],nxt[ans]);
//printf("%d %d ??\n",pos[i],ans);
} /*int now = -1;
for(int i=1;i<=n;i++)
{
if(nxt[i] != -1) now = max(now,nxt[i]);
else
{
nxt[i] = now;
if(now == i) now = -1;
}
}*/
//----------------------处理线段-------------------------
build(,,n);
//for(int i=1;i<=n;i++) printf("%d !!\n",nxt[i]);
int ans = ;
int ql, qr;
while(q--)
{
scanf("%d%d",&ql,&qr);
ql ^= ans;
qr ^= ans; //if(ql > qr) swap(ql, qr);
/*if(ql < 0) ql = -ql;
if(qr < 0) qr = -qr;
if(ql > qr) swap(ql, qr);
if(ql < 1||ql > n) ql = 1;
if(qr <1 ||qr > n) qr = n; */ //ql = 1,qr = n;
if(ql > qr) swap(ql, qr);
printf("%d\n",ans=solve(ql,qr));
}
}
return ;
}