题解 CF242E 【XOR on Segment】

若玉 · 2019-03-11 15:23:51 · 题解

其实并不需要什么神奇的线段树
首先我们来观察n和m的大小
n<=1e5,m<=5* 1e4
知道了这个
我们再观察一下时限
有4s
然后我们考虑暴力
正常的暴力肯定会TLE
加入快读
还是会TLE

所以我们要用到循环展开大法！！！

我是展到了8次，
就可以轻松愉快的卡过此题啦！！！

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,opt,x,y,z,m,a[N],l;
long long ans;
int read()
{
    int sum=0;char ch=getchar();
    while (ch<'0' || ch>'9') ch=getchar();
    while (ch>='0' && ch<='9')
    {
        sum=sum*10+ch-'0';
        ch=getchar();
    }
    return sum;
}
int main()
{
    n=read();
    for (int i=1;i<=n;i++)
      a[i]=read();
    m=read();
    while (m--)
    {
        opt=read();x=read();y=read();
        if (opt==1)
        {
          ans=0;
          for (int i=x;i<=y;i+=7)
            ans+=a[i]+a[i+1]+a[i+2]+a[i+3]+a[i+4]+a[i+5]+a[i+6],l=i;
          for (int i=l;i<=l+6;i++)
            if (i>y) ans-=a[i];
          printf("%I64d\n",ans);
        }
        else
        {
            z=read();
            for (int i=x;i<=y;i+=7)
            {
              a[i]^=z;
              a[i+1]^=z;
              a[i+2]^=z;
              a[i+3]^=z;
              a[i+4]^=z;
              a[i+5]^=z;
              a[i+6]^=z;
              l=i;
            }
            for (int i=l;i<=l+6;i++)
              if (i>y) a[i]^=z;
        }
    }
    return 0;
}