FZU 2240 Daxia & Suneast's problem-白红宇

FZU 2240 Daxia & Suneast's problem

阅读量：7242 次

发布时间：2019-06-29

本文共 1982 字，大约阅读时间需要 6 分钟。

博弈，$SG$函数，规律，线段树。

这个问题套路很明显，先找求出$SG$函数值是多少，然后异或起来，如果是$0$就后手赢，否则先手赢。修改操作和区间查询的话可以用线段树维护一下区间异或和。

数据那么大，一看就知道$SG$有规律......

先写个小数据的$SG$找规律：

bool f[200];int sg[200];int SG(int x){    memset(f,0,sizeof f);    for(int i=x-1;i>=x/2;i--)    {        if(x-i>i) break;        f[sg[i]]=1;    }    for(int i=0;i<=100;i++)    {        if(f[i]==1) continue;        return i;    }}

View Code

会发现是这样的东西：

LL SG(LL x){    if(x%2==0) return x/2;    return SG(x/2);}

View Code

注意：$FZU$上$\% lld$会出问题，我用交才过的。

#pragma comment(linker, "/STACK:1024000000,1024000000")#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          #include
           
            #include
            
             #include
             
              #include
              
               using namespace std;typedef long long LL;const double pi=acos(-1.0),eps=1e-8;void File(){ freopen("D:\\in.txt","r",stdin); freopen("D:\\out.txt","w",stdout);}template 
               
                inline void read(T &x){ char c = getchar(); x = 0;while(!isdigit(c)) c = getchar(); while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); }}LL SG(LL x){ if(x%2==0) return x/2; return SG(x/2);}const int maxn=100010;int n,m;LL s[4*maxn];void build(int l,int r,int rt){ s[rt]=0; if(l==r) { scanf("%lld",&s[rt]); s[rt]=SG(s[rt]); return; } int m=(l+r)/2; build(l,m,2*rt); build(m+1,r,2*rt+1); s[rt]=s[2*rt]^s[2*rt+1];}void update(int p,LL v,int l,int r,int rt){ if(l==r) { s[rt]=v; return;} int m=(l+r)/2; if(p<=m) update(p,v,l,m,2*rt); else update(p,v,m+1,r,2*rt+1); s[rt]=s[2*rt]^s[2*rt+1];}LL get(int L,int R,int l,int r,int rt){ if(L<=l&&r<=R) return s[rt]; int m=(l+r)/2; LL x1=0,x2=0; if(L<=m) x1=get(L,R,l,m,2*rt); if(R>m) x2=get(L,R,m+1,r,2*rt+1); return x1^x2;}int main(){ while(~scanf("%d%d",&n,&m)) { build(1,n,1); for(int i=1;i<=m;i++) { int p,L,R; LL x; scanf("%d%lld%d%d",&p,&x,&L,&R); x=SG(x); update(p,x,1,n,1); LL y=get(L,R,1,n,1); if(y) printf("daxia\n"); else printf("suneast\n"); } } return 0;}