2015 Multi-University Training Contest 2 hdu 5306 Gorgeous Sequence

Gorgeous Sequence

Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 349 Accepted Submission(s): 57

Problem Description

There is a sequence

Input

The first line of the input is a single integer

Output

For every operation of type

Sample Input

5 5

1 2 3 4 5

1 1 5

2 1 5

0 3 5 3

1 1 5

2 1 5

Sample Output

Hint

Please use efficient IO method

Source

2015 Multi-University Training Contest 2

解题：线段树，对着标程写的，还是没搞清到底是怎么回事

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 const int maxn = 1000010;
 5 struct node {
 6     int cover,s,tag,maxtag,maxv;
 7     LL sum;
 8 } tree[maxn<<2];
 9 node put(node c,int t) {
10     if(!t) return c;
11     if(c.cover != c.s) c.maxv = t;
12     c.maxtag = t;
13     c.sum += (LL)t*(c.s - c.cover);
14     c.cover = c.s;
15     return c;
16 }
17 node calc(const node &a,const node &b,int t) {
18     node c;
19     c.tag = t;
20     c.s = a.s + b.s;
21     c.sum = a.sum + b.sum;
22     c.cover = a.cover + b.cover;
23     c.maxv = max(a.maxv,b.maxv);
24     c.maxtag = max(a.maxtag,b.maxtag);
25     return put(c,t);
26 }
27 int tmp,n,m;
28 void build(int L,int R,int v) {
29     tree[v].tag = 0;
30     tree[v].s = R - L + 1;
31     if(L == R) {
32         scanf("%d",&tmp);
33         tree[v].sum = tree[v].tag = tree[v].maxtag = tree[v].maxv = tmp;
34         tree[v].cover = 1;
35         return;
36     }
37     int mid = (L + R)>>1;
38     build(L,mid,v<<1);
39     build(mid+1,R,v<<1|1);
40     tree[v] = calc(tree[v<<1],tree[v<<1|1],0);
41 }
42 node query(int L,int R,int lt,int rt,int v) {
43     if(lt <= L && rt >= R) return tree[v];
44     int mid = (L + R)>>1;
45     if(rt <= mid) return put(query(L,mid,lt,rt,v<<1),tree[v].tag);
46     if(lt > mid) return put(query(mid+1,R,lt,rt,v<<1|1),tree[v].tag);
47     return calc(query(L,mid,lt,rt,v<<1),query(mid+1,R,lt,rt,v<<1|1),tree[v].tag);
48 }
49 void cleartag(int v,int t) {
50     if(tree[v].maxtag < t) return;
51     if(tree[v].tag >= t) tree[v].tag = 0;
52     if(tree[v].s > 1) {
53         cleartag(v<<1,t);
54         cleartag(v<<1|1,t);
55     }
56     if(tree[v].s == 1) {
57         tree[v].sum = tree[v].maxtag = tree[v].maxv = tree[v].tag;
58         tree[v].cover = (tree[v].tag > 0);
59     } else tree[v] = calc(tree[v<<1],tree[v<<1|1],tree[v].tag);
60 }
61 void update(int L,int R,int lt,int rt,int t,int v) {
62     if(tree[v].tag && tree[v].tag <= t) return;
63     if(lt <= L && rt >= R) {
64         cleartag(v,t);
65         tree[v].tag = t;
66         if(L == R) {
67             tree[v].sum = tree[v].tag = tree[v].maxv = tree[v].maxtag = t;
68             tree[v].cover = (tree[v].tag > 0);
69         } else tree[v] = calc(tree[v<<1],tree[v<<1|1],t);
70     } else {
71         int mid = (L + R)>>1;
72         if(rt <= mid) update(L,mid,lt,rt,t,v<<1);
73         else if(lt > mid) update(mid+1,R,lt,rt,t,v<<1|1);
74         else {
75             update(L,mid,lt,rt,t,v<<1);
76             update(mid+1,R,lt,rt,t,v<<1|1);
77         }
78         tree[v] = calc(tree[v<<1],tree[v<<1|1],tree[v].tag);
79     }
80 }
81 int main() {
82     int kase,op,x,y,t;
83     scanf("%d",&kase);
84     while(kase--) {
85         scanf("%d%d",&n,&m);
86         build(1,n,1);
87         while(m--) {
88             scanf("%d%d%d",&op,&x,&y);
89             if(!op) {
90                 scanf("%d",&t);
91                 update(1,n,x,y,t,1);
92             } else if(op == 1) printf("%d
",query(1,n,x,y,1).maxv);
93             else printf("%I64d
",query(1,n,x,y,1).sum);
94         }
95     }
96     return 0;
97 }

View Code

哥终于搞清了，感谢某岛的代码

本题的做法有点类似于天龙八部里面虚竹那个下棋场景，死而后生

做法就是：每次更新一段区间的时候，把标记放到本区间，然后，我们要兵马未动，粮草先行

先去下面走一遭，统计下面有多少个不大于t，并且这些不大于t的元素的和

这样就能计算出当前区间的和了？不能？那么最大值呢？别逗了，当前区间的最大值肯定是t啦。

tag?要么就是0，要么就是区间的最大值。不是么？

你说这样都不超时真没天理？是的，我也是这么觉得的。。。每次都推到底，这还不超时。。。我也不知道分摊是如何分摊的

下面是搞清真相后写的另一份代码，代码内附有注释，我想这是你目前所能看到的最详细的解说了，毕竟中学生写的代码，可能是有代沟吧

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 typedef long long LL;
  4 const int maxn = 1001010;
  5 struct node{
  6     LL sum;
  7     int cv,mx,tag;
  8     //cv用来记录该区间有多少个数不大于t
  9     //mx当然是记录区间的最大值
 10     //tag是lazy标识啦，这个线段树常客
 11     //sum...
 12 }tree[maxn<<2];
 13 void pushup(int v){
 14     tree[v].sum = tree[v<<1].sum + tree[v<<1|1].sum;
 15     tree[v].mx = max(tree[v<<1].mx,tree[v<<1|1].mx);
 16     tree[v].cv = tree[v<<1].cv + tree[v<<1|1].cv;
 17 }
 18 int tmp;
 19 void build(int lt,int rt,int v){
 20     if(lt == rt){
 21         scanf("%d",&tmp);
 22         tree[v].sum = tree[v].mx = tree[v].tag = tmp;
 23         tree[v].cv = 1;
 24         //cv记录的是不大于t的元素个数
 25         return;
 26     }
 27     tree[v].tag = 0;
 28     int mid = (lt + rt)>>1;
 29     build(lt,mid,v<<1);
 30     build(mid+1,rt,v<<1|1);
 31     pushup(v);
 32 }
 33 void modify(int L,int R,int t,int v){
 34     if(tree[v].tag && tree[v].tag <= t) return;
 35     tree[v].tag = t;
 36     //只有可能是tree[v].tag  == 0
 37     //因为前面calc的时候已经先行走了一遍
 38     if(tree[v].cv != R - L + 1){
 39         //因为当前区间不大于t的元素不算全区间，所以还有比t大的
 40         //大的要置成t，所以mx成了t
 41         tree[v].mx = t;
 42         tree[v].sum += (LL)t*(R - L + 1 - tree[v].cv);
 43         tree[v].cv = R - L + 1;
 44         //sum在alc以后 其实代表的是那些不大于t的元素之和
 45         //现在把大于t的都改成t了，那么现在和是多少？
 46     }
 47 }
 48 void pushdown(int L,int R,int v){
 49     if(tree[v].tag){
 50         int mid = (L + R)>>1;
 51         modify(L,mid,tree[v].tag,v<<1);
 52         modify(mid+1,R,tree[v].tag,v<<1|1);
 53         tree[v].tag = 0;
 54     }
 55 }
 56 void calc(int L,int R,int t,int v){
 57     if(tree[v].mx < t) return;
 58     if(tree[v].tag >= t) tree[v].tag = 0;
 59     if(L == R){
 60         tree[v].sum = tree[v].mx = tree[v].tag;
 61         tree[v].cv = tree[v].tag?1:0;
 62         //记录当前不大于t的元素的个数以及他们的和
 63         return;
 64     }
 65     pushdown(L,R,v);
 66     int mid = (L + R)>>1;
 67     calc(L,mid,t,v<<1);
 68     calc(mid+1,R,t,v<<1|1);
 69     pushup(v);
 70 }
 71 void update(int L,int R,int lt,int rt,int t,int v){
 72     if(tree[v].mx <= t) return;
 73     if(lt <= L && rt >= R){
 74         if(L == R){
 75             tree[v].sum = tree[v].tag = tree[v].mx = t;
 76             tree[v].cv = 1;
 77             //强行修改为t,毕竟此处是大于t的，如果不大于t前面return了
 78         }else calc(L,R,t,v);//先行遍历到底，兵马未动，粮草先行
 79         modify(L,R,t,v);
 80     }else{
 81         pushdown(L,R,v);
 82         int mid = (L + R)>>1;
 83         if(lt <= mid) update(L,mid,lt,rt,t,v<<1);
 84         if(rt > mid) update(mid+1,R,lt,rt,t,v<<1|1);
 85         pushup(v);
 86     }
 87 }
 88 int queryMax(int L,int R,int lt,int rt,int v){
 89     if(lt <= L && rt >= R) return tree[v].mx;
 90     int mid = (L + R)>>1,mx = INT_MIN;
 91     pushdown(L,R,v);
 92     if(lt <= mid) mx = max(mx,queryMax(L,mid,lt,rt,v<<1));
 93     if(rt > mid) mx = max(mx,queryMax(mid+1,R,lt,rt,v<<1|1));
 94     pushup(v);
 95     return mx;
 96 }
 97 LL querySum(int L,int R,int lt,int rt,int v){
 98     if(lt <= L && rt >= R) return tree[v].sum;
 99     int mid = (L + R)>>1;
100     LL sum = 0;
101     pushdown(L,R,v);
102     if(lt <= mid) sum += querySum(L,mid,lt,rt,v<<1);
103     if(rt > mid) sum += querySum(mid+1,R,lt,rt,v<<1|1);
104     pushup(v);
105     return sum;
106 }
107 int main(){
108     int kase,n,m,op,x,y,t;
109     scanf("%d",&kase);
110     while(kase--){
111         scanf("%d%d",&n,&m);
112         build(1,n,1);
113         while(m--){
114             scanf("%d%d%d",&op,&x,&y);
115             if(x > y) swap(x,y);
116             if(!op){
117                 scanf("%d",&t);
118                 update(1,n,x,y,t,1);
119             }else if(op == 1) printf("%d
",queryMax(1,n,x,y,1));
120             else printf("%I64d
",querySum(1,n,x,y,1));
121         }
122     }
123     return 0;
124 }

View Code