HDU-6356 Glad You Came (线段树)

题意：数组有n个数初始为0，m个询问，每个询问给出L R V（按照给定函数生成），将数组的下标L到R的数与V取较大值，最后输出给定的公式结果。

题意：哇~打比赛的时候想用两个线段树去维护，一棵维护每个结点所代表区间的最大值，一棵维护每个结点所代表区间的异或和。不过这题比我想的要暴力~~~直接维护最大值，最后遍历整棵树将最大值pushdown下去就可以了。~

 1 #include <bits/stdc++.h>
 2 #define pi acos(-1)
 3 #define fastcin ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
 4 using namespace std;
 5 typedef long long LL;
 6 typedef pair<int, int> PII;
 7 const int INF = 0x3f3f3f3f;       // 不能加负号！！！
 8 const LL LL_INF = 0x3f3f3f3f3f3f3f3f;//4e18 ~= 2^62
 9 const int maxn =100000 + 10;
10 const LL mod = pow(2, 30);
11 LL maxx[maxn<<2];
12 LL a[maxn];
13 LL ans ;
14 unsigned int RNG61(unsigned int &x, unsigned int &y, unsigned int &z)
15 {
16     x = x^(x<<11);
17     x = x^(x>>4);
18     x = x^(x<<5);
19     x = x^(x>>14);
20     unsigned int w = x^(y^z);
21     x = y;
22     y = z;
23     z = w;
24     return z;
25 }
26 
27 void PushDown(int rt)
28 {
29     maxx[rt<<1] = max(maxx[rt<<1],maxx[rt]);
30     maxx[rt<<1|1] = max(maxx[rt<<1|1],maxx[rt]);
31 }
32 
33 //区间更新，假设A[L,R]+=C
34 void update(int L, int R, LL v, int l, int r, int rt)
35 {
36     //cout<<l<<"____"<<r<<"....."<<rt<<endl;
37     if(maxx[rt] > v) return;
38     if(L<=l && r<=R){
39         maxx[rt] = max(maxx[rt],v);
40         return ;
41     }
42     int mid = (l+r)>>1;
43     PushDown(rt);
44     if(L <= mid) update(L, R, v, l, mid, rt<<1);
45     if(R >  mid) update(L, R, v, mid+1, r, rt<<1|1);
46 //    PushUp(rt);
47 }
48 void get(int l,int r,int rt){
49     if(l == r){
50         ans ^= l*maxx[rt];
51         return ;
52     }
53     PushDown(rt);
54     int mid = (l+r)>>1;
55     get(l,mid,rt<<1);
56     get(mid+1,r,rt<<1|1);
57 }
58 int main()
59 {
60     int T;
61     cin>>T;
62     while(T--){
63         int n, m, l, r, v;
64         memset(maxx,0,sizeof(maxx));
65         memset(a,0,sizeof(a));
66         unsigned int X, Y, Z;
67         scanf("%d%d%u%u%u", &n, &m, &X, &Y, &Z);
68         unsigned int t1, t2, t3;
69         for(int i=0; i<m; i++){
70             t1 = RNG61(X, Y, Z);
71             t2 = RNG61(X, Y, Z);
72             t3 = RNG61(X, Y, Z);
73             l = min((t1%n)+1, (t2%n)+1);
74             r = max((t1%n)+1, (t2%n)+1);
75             v = (t3 % mod + mod) %mod;
76             update(l, r, v, 1, n, 1);
77         }
78         ans = 0;
79         get(1,n,1);
80         printf("%lld
", ans);
81     }
82 }