题解 | #小 Q 与异或#

题解 小 Q 与异或
牛客练习赛? DIV1!
给你异或方程组的一些方程解，要求构造出异或方程组的全部解
性质一：
如果有两个方程右端点相同而解值不相同，则方程组不存在解
性质二：异或的逆元为其本身
利用性质二可通过x^y=z ->x^y^y逆=z^y逆 -> x=z^y逆 ->x=z^y解逆元方程

情况一：区间右端点相等但x值不相等 输出-1
情况二：异或逆元为0才能使异或方程成立 违反题目要求 输出-1
但情况二除非给你两组右端点差值为1且x值相同，否者是必定能构造出来的，因为x的范围为1e9，而答案数组的范围为2e10，所以在没有区间约束的情况下可以使用2^31和2^30左右横跳，无论给你什么x值因为小于目前的异或和,所以必定不会使异或逆元为0，即必定是存在解的

#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
const int N=1e6+5;
struct node
{
    int r;
    int val; 
}e[1000005];
struct cmp
{
    bool operator()(const node&t1,const node&t2)
    {
        if(t1.r!=t2.r)
        return t1.r<t2.r;
        return t1.val<t2.val;
    }
};
long long ans[1000005];
int main()
{
    long long che=pow(2,31);
    int n,m,flag=0,count=1;
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++)
    {
        scanf("%d%d",&e[i].r,&e[i].val);
    }
    sort(e,e+m,cmp());//先排个序，按递增右端点性质通过递推处理区间
    int old=0,arr=0,old2=0;
    long long bas;long long s=0;//bas  当前异或方程的解  s   异或方程的总异或和 
    for(int i=1;i<e[0].r;i++)//处理前边界 
    {
        bas=che;
        ans[arr++]=che;
        s^=che;
        old=i;
        old2=bas;
        if(count==1)//左右横跳填充 
        {
            count=0;
            che/=2;
        }
        else {
            count=1;
            che*=2;
        }
    }

    for(int i=0;i<m;i++)
    {
        int t=e[i].r;
        if(t==old&&old2==e[i].val)
        continue;
        else if(t==old&&old2!=e[i].val)
        {
            flag=1;
            break;
        }
        if(arr==0)
        {
            s=bas=ans[arr++]=e[i].val;
            if(bas==0)//处理第一位为0的情况 
            {
                flag=1;
                break;
            }
        }
        else {
            if(t-old>1)//左右横跳填充区间缝隙 
            {
                for(int j=0;j<t-old-1;j++)
                {
                    bas=che;
                    s^=bas;
                    ans[arr++]=che;    
                    if(count==1)
                    {        
                        count=0;
                        che/=2;
                    }
                    else {
                        count=1;
                        che*=2;
                    }
        //            printf("%lld\n",bas);
                }
                bas=s^e[i].val;
                s=e[i].val;
                if(bas==0)
                {
                    flag=1;
                    break;
                }
                ans[arr++]=bas;
            }
            else {
                bas=s^e[i].val;
                s=e[i].val;
                if(bas==0)
                {
                    flag=1;
                    break;
                }
                ans[arr++]=bas;
            }
        }
    //    printf("%lld\n",bas);
        old2=e[i].val;
        old=e[i].r;
    }
    if(flag==1)
    {
        printf("-1\n");
        return 0;
    }
    for(int i=0;i<arr;i++)
    {
        printf("%lld ",ans[i]);
    }
    for(int i=arr;i<n;i++) //左右横跳填充右区间 
    {
        printf("%lld ",che);
        if(count==1)
        {
            count=0;
            che/=2;
        }
        else {
            count=1;
            che*=2;
        }
    }
    printf("\n");
 } 
/*
5 4
1 5
2 4
3 15
4 62

5 3
1 2
2 6
2 4

5 3
3 4
3 4
4 6

6 3
5 4 
5 4
5 4

6 1
3 0


*/