Description

法法塔和wyl8899都喜欢玩游戏。但是每次玩游戏法法塔都被wyl8899虐。

为了安慰可怜的法法塔，wyl8899决定大发慈悲，修改了一下游戏规则。

是这样的，这儿有一堆石子排成一列，每次wyl8899让hza选择一个区间进行游戏。游戏嘛，就是采用最普通的规则：两人轮流操作，每次选择一堆石子，取掉不为0的石子数，没法操作者失败。法法塔要做的是这样的：

我们现在定义一个区间的弱菜值：表示如果法法塔先取石子，而且法法塔第一步取的石子规定是最右边的那堆的话，为了必胜，第一步需要取的石子数。如果没法获胜的话，那么弱菜值就是-1。

法法塔要选择一个区间[l,r]，使得r为wyl8899给定的某个数，l属于[a,b]，a，b也是wyl8899给定的，要求这个区间的弱菜值是满足前面的条件中最大。请给出这个最大的弱菜值。

如果最大弱菜值不为-1，法法塔就会马上取走该区间最右端的石子堆最大弱菜值数量的石子。

 

 

Input

第一行一个正整数n，描述了石子的堆数，接下来一行n个数，描述每堆石子的数目。

接下来一行m，表示将进行要进行m次游戏，每次游戏由三个值刻画，r,a,b。r表示被选定的右端点，[a,b]表示选择的区间的左端点的范围

Output

对于每个询问输出最大的弱菜值。

 

Sample Input

输入1： 12 662 477 125 483 17 560 232 59 176 928 807 659 5 5 2 5 4 4 4 2 1 2 6 4 6 6 2 3 输入2： 7 230 883 456 1020 966 899 610 2 7 1 2 2 1 2 输入3： 11 392 808 14 71 393 79 11 74 713 232 142 5 8 3 8 9 5 9 3 1 1 8 2 8 7 4 6  

Sample Output

输出1： 17 483 477 560 -1 输出2： 352 883 输出3： 74 713 -1 -1 -1  

 

Data Constraint

n<=100000，m<=10000，每堆的石子数<=1000。

分析

取火柴游戏，发现就是要求s[r-1]^s[x] （a<=x<=b）最小

s是异或前缀和，s[r-1]是固定的，求s[x]

那么我们看到异或的题目可以考虑trie，可是区间询问的问题一颗trie怎么搞？

那么我们利用分块加trie可以随便切完这题，在trie上找答案时可以从高位开始找异或值为0贪心，正确性显然

然鹅我打的是n^2暴力也过了

 

#include 
      
       #include 
       
        #include 
        
         using namespace std;const int N=5e5+10;int n,m,s[N];int main() {     scanf("%d",&n);    for (int i=1;i<=n;i++) scanf("%d",&s[i]);    scanf("%d",&m);    for (int i=1;i<=m;i++) {        int R,A,B,k,ans=0;        scanf("%d%d%d",&R,&A,&B);        if (s[R]==0) {            printf("-1\n");            continue;        }        if (R==B) {            printf("%d\n",s[R]);            s[R]=0;            continue;        }        k=0;        for (int j=R-1;j>=A;j--) {            k^=s[j];            if (B>=j&&s[R]>=k) ans=max(ans,s[R]-k);            if (ans==s[R]) break;        }        if (ans==0) printf("-1\n");        else printf("%d\n",ans);        s[R]-=ans;    }}