2018HDU多校五-G题 Glad You Game (线段树)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6356 　　　　　　　　　　　

　　　　　　　　　　　　　　　　　　　　　　　　　Glad You Game

Steve has an integer array

a

a

⎧⎩⎨ l i r i v i = min ((f 3 i - 2 mod n) + 1, (f 3 i

InputThe first line contains one integer $T$ OutputFor each test case, output the answer in one line.
Sample Input

4
1 10 100 1000 10000
10 100 1000 10000 100000
100 1000 10000 100000 1000000
1000 10000 100000 1000000 10000000

Sample Output

1031463378
1446334207
351511856
47320301347

Hint

In the first sample, a = [1031463378] after all the operations.
In the second sample, a = [1036205629, 1064909195, 1044643689, 1062944339, 1062944339, 1062944339, 1062944339, 1057472915, 1057472915, 1030626924] after all the operations.

        
题意：给你一个生成L,R,V 的函数，让你对区间L~R的数，把小于v的数都变为v,最后求所有数的异或；
题解：我们利用线段树维护每一段区间的最大值，最小值，对于一段区间L~R，如果最大值都小于V，那么久更新整个区间，如果最小值都大于V，就不操作；最后暴力查找每个位置的数异或求值即可；
参考代码：

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 typedef long long LL;
  4 const int maxn=1e5+10;
  5 int n,m,T;
  6 unsigned int X,Y,Z;
  7 
  8 struct Node{
  9     int l,r,maxnum,minnum,tag;
 10 } tree[maxn<<2];
 11 
 12 unsigned int functions()
 13 {
 14     X=X^(X<<11);
 15     X=X^(X>>4);
 16     X=X^(X<<5);
 17     X=X^(X>>14);
 18     unsigned int w=X^(Y^Z);
 19     X=Y; Y=Z; Z=w;
 20     return Z;
 21 }
 22 
 23 void build(int pos,int l,int r)
 24 {
 25     tree[pos].l=l,tree[pos].r=r,tree[pos].tag=-1;
 26     if(l==r) 
 27     {
 28         tree[pos].maxnum=0;
 29         tree[pos].minnum=0;
 30         return ;
 31     }
 32     int mid=(tree[pos].l+tree[pos].r)>>1;
 33     build(pos<<1,l,mid);
 34     build(pos<<1|1,mid+1,r);
 35     tree[pos].maxnum=max(tree[pos<<1].maxnum,tree[pos<<1|1].maxnum);
 36     tree[pos].minnum=min(tree[pos<<1].minnum,tree[pos<<1|1].minnum);
 37 }
 38 
 39 void pushup(int pos)
 40 {
 41     tree[pos].maxnum=max(tree[pos<<1].maxnum,tree[pos<<1|1].maxnum);
 42     tree[pos].minnum=min(tree[pos<<1].minnum,tree[pos<<1|1].minnum);
 43 }
 44 
 45 void pushdown(int pos)
 46 {
 47     tree[pos<<1].maxnum=max(tree[pos<<1].maxnum,tree[pos].tag);
 48     tree[pos<<1|1].maxnum=max(tree[pos<<1|1].maxnum,tree[pos].tag);
 49     tree[pos<<1].minnum=max(tree[pos<<1].minnum,tree[pos].tag);
 50     tree[pos<<1|1].minnum=max(tree[pos<<1|1].minnum,tree[pos].tag);
 51     tree[pos<<1].tag=max(tree[pos<<1].tag,tree[pos].tag);
 52     tree[pos<<1|1].tag=max(tree[pos<<1|1].tag,tree[pos].tag);
 53     tree[pos].tag=-1;
 54 }
 55 
 56 void update(int pos,int l,int r,int val)
 57 {
 58     if(tree[pos].l==tree[pos].r) 
 59     {
 60         tree[pos].maxnum=max(tree[pos].maxnum,val);
 61         tree[pos].minnum=max(tree[pos].minnum,val);
 62         return ;
 63     }
 64     if(tree[pos].l>=l&&tree[pos].r<=r) 
 65     {
 66         if(tree[pos].maxnum<=val)
 67         {
 68             tree[pos].maxnum=tree[pos].minnum=val;
 69             tree[pos].tag=max(tree[pos].tag,val);
 70             return ;
 71         }
 72     }
 73     if(tree[pos].minnum>=val) return ;
 74     
 75     if(tree[pos].tag!=-1) pushdown(pos);
 76     int mid=(tree[pos].l+tree[pos].r)>>1;
 77     if(r<=mid) update(pos<<1,l,r,val);
 78     else if(l>=mid+1) update(pos<<1|1,l,r,val);
 79     else update(pos<<1,l,mid,val),update(pos<<1|1,mid+1,r,val);
 80     pushup(pos);    
 81 }
 82 
 83 int query(int pos,int k)
 84 {
 85     if(tree[pos].l==tree[pos].r&&tree[pos].l==k) return tree[pos].maxnum;
 86     int mid=(tree[pos].l+tree[pos].r)>>1;
 87     if(tree[pos].tag!=-1) pushdown(pos);
 88     if(k<=mid) return query(pos<<1,k);
 89     else return query(pos<<1|1,k);
 90 }
 91 
 92 int main()
 93 {
 94     ios::sync_with_stdio(false);
 95     cin.tie(0);
 96     cin>>T;
 97     while(T--)
 98     {
 99         LL ans=0;
100         cin>>n>>m>>X>>Y>>Z;
101         build(1,1,n);
102         for(int i=1;i<=m;i++)
103         {
104             int l=functions()%n+1;
105             int r=functions()%n+1;
106             int v=functions()%(1<<30);
107             if(l>r) swap(l,r);
108             update(1,l,r,v);
109         }
110         for(int i=1;i<=n;i++) ans^=1ll*i*query(1,i);
111         cout<<ans<<endl;
112     }
113     
114     return 0;
115 }

View Code