[原创]HDU 5239 Doom [线段树,更新有上界]【数据结构】

2017-08-03 22:57:34 Tabris_ 阅读数：461

博客爬取于2020-06-14 22:39:30
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/76158441

好久没有更新博客了 更新一波吧，，，

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

——————————————————————————————————————

Doom

Time Limit: 12000/6000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 1524 Accepted Submission(s): 419

Problem Description
THE END IS COMINGGGGGG!

Mike has got stuck on a mystery machine. If he cannot solve this problem, he will go to his doom.

This machine is consist of n cells, and a screen. The i-th cell contains a number ai(1≤i≤n). The screen also contains a number s, which is initially 0.

There is a button on each cell. When the i-th is pushed, Mike observes that, the number on the screen will be changed to s+ai, where s is the original number. and the number on the i-th cell will be changed to a2i.

Mike observes that the number is stored in radix p, where p=9223372034707292160. In other words , the operation is under modulo p.

And now, Mike has got a list of operations. One operation is to push buttons between from l-th to r-th (both included), and record the number on the screen. He is tired of this stupid work, so he asks for your help. Can you tell him, what are the numbers recorded.

Input
The first line contains an integer T(T≤5), denoting the number of test cases.

For each test case, the first line contains two integers n,m(1≤n,m≤105).

The next line contains n integers ai(0≤ai< p), which means the initial values of the n cells.

The next m lines describe operations. In each line, there are two integers l,r(1≤l≤r≤n), representing the operation.

Output
For each test case, output ‘‘Case #t:’’, to represent this is the t-th case. And then output the answer for each query operation, one answer in a line.

For more details you can take a look at the example.

Sample Input
2
4 4
2 3 4 5
1 2
2 3
3 4
1 4
1 3
2
1 1
1 1
1 1

Sample Output
Case #1:
5
18
39
405
Case #2:
2
6
22

-------------------------------------------------------.

题目大意:
给你一个序列,每个序列有一个值.

每次选择一个区间,将这个区间的数的和加起来,然后让这个区间的每个数都平方.

所有数都是对9223372034707292160取模的

注意这个模数，和正常的模数不一样，那么就一定有问题

然后通过打表能发现，每个数不断自身平方对p取模后经过有限次 就不会变化了，

测试少于30次

所以也就是说每个节点至多会被更新30次，

所以可以直接维护线段树，打上平方标记后，还要打一个标记表示这个区间的数已经不会变化了，这样这个位置就不用再更新了

这样的话 复杂度就是O(nlog⁡n∗30)O(n\log n *30)

附本题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
# include <bits/stdc++.h>
typedef unsigned long long int LLu;
typedef unsigned __int64 LL;
using namespace std;

const int N   = 100000+7;
const LL  MOD = (LL)9223372034707292160 ;

# define lal puts("****");
# define pb push_back
# define mp make_pair

inline int read(){
    int x = 0,f=1;char ch = getchar();
    for(;ch<'0'||'9'<ch;ch=getchar()) if(ch == '-') getchar();
    for(;'0'<=ch&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+ch-'0';
    return x*f;
}

/********************************************************/
int n,m,x;
LL a[N];
LL qmul(LL a,LL b){
    LL res = 0;
    while(b){
        if(b&1) res=(res+a)%MOD;
        b>>=1,a=(a+a)%MOD;
    }
    return res;
}

LL sum[N<<2];
bool vis[N<<2];
void pushup(int rt){
    vis[rt]=vis[rt<<1]&vis[rt<<1|1];
    sum[rt]=(sum[rt<<1]+sum[rt<<1|1])%MOD;
}
void build(int rt,int l,int r){
    sum[rt]=0,vis[rt]=false;
    if(l==r) {sum[rt]=a[l];return ;}
    int m = r+l >>1;
    build(rt<<1  ,l  ,m);
    build(rt<<1|1,m+1,r);
    pushup(rt);
}

void update(int rt,int l,int r,int L,int R){
    if(vis[rt]&&L<=l&&r<=R)return ;
    if(l==r){
        LL tmp = qmul(sum[rt],sum[rt]);
        if(tmp == sum[rt]) vis[rt]=true;
        sum[rt]=tmp;
        return ;
    }
    int m =r+l >> 1;
    if(L<=m) update(rt<<1  ,l  ,m,L,R);
    if(R> m) update(rt<<1|1,m+1,r,L,R);
    pushup(rt);
}

LL query(int rt,int l,int r,int L,int R){
    if(L<=l&&r<=R) return sum[rt];
    int m = r+l >> 1;
    LL ans = 0;
    if(L<=m) ans+= query(rt<<1  ,l  ,m,L,R),ans%=MOD;
    if(R> m) ans+= query(rt<<1|1,m+1,r,L,R),ans%=MOD;
    return ans;
}

int main(){
//    cout << MOD << endl;
//    for(int i=2;i<=10;i++){
//        LL x=i;
//        for(int j=1;j<=100;j++){
//            cout<<x<<"\n";
//            x=qmul(x,x);
//        }
//        puts("-------------------------------");
//    }

    int _ = 1,kcase = 0;
    for(scanf("%d",&_);_--;){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++) scanf("%llu",&a[i]);
        LL ans = 0;
        build(1,1,n);
        printf("Case #%d:\n",++kcase);
        for(int l,r;m--;){
            scanf("%d%d",&l,&r);
            ans += query(1,1,n,l,r);ans%=MOD;
            update(1,1,n,l,r);
            printf("%llu\n",ans);
        }
    }
    return 0;
}