HDU Multi-School Training in 2019-Operation

General meaning: Give n numbers, and then m operations, operation type has 1 operation or 0 operation. 0 is the query operation, 1 is the addition of digital operations. Assuming that the result of each query is ans, the 0 operation is to add a digit x^ans to the digit XOR maximum of the query (l^ans)%n+1 interval (if l^ans)%n+1 is greater than (r^ans)%n+1), and the 1 operation is to add a digit x^ans to the n digits. If you know the prefix linear basis, then this question is not interesting.

Code:

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+100;
int cur;
struct node
{
    int line_base[32],pos[32];
}prefix_line_base[maxn];
bool Insert(int x)
{
    ++cur;
    prefix_line_base[cur]=prefix_line_base[cur-1];
    int p=cur;
    for(int i=31;i>=0;--i)
    {
        if(x&(1LL<<i))
        {
            if(!prefix_line_base[cur].line_base[i])
            {
                prefix_line_base[cur].line_base[i]=x;
                prefix_line_base[cur].pos[i]=p;
                break;
            }
            else
            {
                if(prefix_line_base[cur].pos[i]<p)
                    swap(prefix_line_base[cur].pos[i],p),swap(prefix_line_base[cur].line_base[i],x);
                x^=prefix_line_base[cur].line_base[i];
            }
        }
    }
}
int Query(int l,int r)
{
    int ans=0;
    for(int i=31;i>=0;--i)
    {
        if(prefix_line_base[r].pos[i]>=l)
        {
            if((ans^prefix_line_base[r].line_base[i])>ans)
                ans^=prefix_line_base[r].line_base[i];
        }
    }
    return ans;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        cur=0;
        memset(prefix_line_base,0,sizeof(prefix_line_base));
        int n,m,x;
        scanf("%d %d",&n,&m);
        for(int i=1;i<=n;++i)
        {
            scanf("%d",&x);
            Insert(x);
        }
        int opt;
        int ans=0,l,r;
        while(m--)
        {
            scanf("%d",&opt);
            if(!opt)
            {
                scanf("%d %d",&l,&r);
                l=(l^ans)%cur+1;
                r=(r^ans)%cur+1;
                if(l>r)
                    swap(l,r);
                ans=Query(l,r);
                printf("%d\n",ans);
            }
            else
            {
                scanf("%d",&x);
                x^=ans;
                Insert(x);
            }
        }
    }
    return 0;
}

 

Posted on Sun, 06 Oct 2019 18:03:07 -0700 by coreycollins