2019HDU多校第一场 1009 String 线性基+历史版本更新

末蓝、 2021-11-27 02:26 221阅读 0赞

这个题的意思是，任意给你区间，然后求区间的异或和最大值。

和线性基模板不一样，这个是任意区间！！

题目：[http://acm.hdu.edu.cn/showproblem.php?pid=6579][http_acm.hdu.edu.cn_showproblem.php_pid_6579]

如果按照模板做法，对每个区间遍历一遍然后去求(线性基不支持删除操作)。那么，N方的复杂度就会爽歪歪。

看了题解：是使用一个pos记录线性基的每个元素的历史版本是多少，使一个二维数组记录每个历史版本的情况。

线性基学的不是太好，请教了学长，但是自己高斯消元不是太清楚，线性基又要使用高斯的思想，就没好意思继续请教，贴代码吧。

#include<bits/stdc++.h>
    using namespace std;
    const int MAXN=500000+10;
    int T,n,m,op,l,r,tmp,ans,a[MAXN],f[MAXN][32],pos[MAXN][32];
    inline int Read() 
    {
        int x=0,f=1; char ch=getchar(); 
        while (ch<'0'||ch>'9') {if (ch=='-') f=-f; ch=getchar();}
        while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
        return x*f;
    }
    char s[30];
    inline void writeln(int x)
    {
    	if (x<0) putchar('-'),x=-x; 
    	if (!x) putchar('0'); else 
    	{
    	    int len=0;  
    	    while (x) s[++len]=x%10+'0',x/=10;
    	  	while (len) putchar(s[len--]);
    	} 
    	putchar('\n');
    }
    inline void Add(int i,int x)
    {
    	int k=i;
    	for (int j=30;j>=0;--j) f[i][j]=f[i-1][j],pos[i][j]=pos[i-1][j];
    	for (int j=30;j>=0;--j) if (x>>j) 
    	{
    		if (!f[i][j])
    		{
    			f[i][j]=x;
    			pos[i][j]=k;//记录当前位的距离 
    			break;
    		}else{
    			if (k>pos[i][j]) //保持每一位是最后一次更新 
    			{
    				tmp=k,k=pos[i][j],pos[i][j]=tmp;  
    				tmp=x,x=f[i][j],f[i][j]=tmp;  
    			}
                x^=f[i][j];
    		}
    	}
    }
    int main()
    {
    	T=Read();//测试样例数量 
    	while (T--)
    	{
    		n=Read(),m=Read();
    		for (int i=1;i<=n;++i) a[i]=Read(),Add(i,a[i]);//读取数据。 不仅插入线性基，还记录每次插入的位置 
    		ans=0;
    	    while (m--)
    	    {
    	    	op=Read();
    	    	if (op) a[++n]=Read()^ans,Add(n,a[n]);//向末尾插入线性基 
    			else
    			{
    				l=Read(),r=Read();//读入区间 
    				l=(l^ans)%n+1,r=(r^ans)%n+1;
    				if (l>r) swap(l,r);
                    ans=0;
                    for (int j=30;j>=0;--j) if((ans^f[r][j])>ans&&pos[r][j]>=l) ans^=f[r][j];//如果这一位比较大，并且这一位的最后一次更新大于左边区间的历史版本，
                    writeln(ans);
    			}
    		}
    		for (int i=1;i<=n;++i)
    		  for (int j=30;j>=0;--j) f[i][j]=pos[i][j]=0;//初始化，条件 
    	}
    	return 0;
    }
    //本题使用线性基来写，但是不仅仅插入线性基，还记录线性基插入的位置，开一个数组来写，这样不用使用线段树来开线性基

[http_acm.hdu.edu.cn_showproblem.php_pid_6579]: http://acm.hdu.edu.cn/showproblem.php?pid=6579