hdu 3308 LCIS

本文从WordPress迁移而来, 查看全部WordPress迁移文章

线段树

相对于UESTC 1425来讲,在更新上简单了,因为是单点更新

查询是一样的区间查询。记录的信息是一样

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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 100010
#define lson(i) ((i)<<1)
#define rson(i) ((i)<<1|1)

struct SegTree{
int l,r,mid,len;
int Max;
int first,pl;
int last,sl;
SegTree(){}
SegTree(int __l,int __r){
l = __l; r = __r; mid = (l+r)>>1; len = r-l+1;
first = last = pl = sl = 0; Max = 0;
}
}t[N<<2];

void PushUp(int rt){
t[rt].first = t[lson(rt)].first;
t[rt].last = t[rson(rt)].last;
t[rt].pl = t[lson(rt)].pl;
t[rt].sl = t[rson(rt)].sl;
if(t[lson(rt)].pl == t[lson(rt)].len && t[lson(rt)].last < t[rson(rt)].first){
t[rt].pl = t[lson(rt)].pl + t[rson(rt)].pl;
}
if(t[rson(rt)].sl == t[rson(rt)].len && t[lson(rt)].last < t[rson(rt)].first){
t[rt].sl = t[lson(rt)].sl + t[rson(rt)].sl;
}
t[rt].Max = max(t[lson(rt)].Max , t[rson(rt)].Max);
if(t[lson(rt)].last < t[rson(rt)].first){
t[rt].Max = max(t[rt].Max,t[lson(rt)].sl + t[rson(rt)].pl);
}
}

void Do(SegTree &res,SegTree res1,SegTree res2){
res.first = res1.first;
res.last = res2.last;
res.pl = res1.pl;
res.sl = res2.sl;
if(res1.pl == res1.len && res1.last < res2.first){
res.pl = res1.pl + res2.pl;
}
if(res2.sl == res2.len && res1.last < res2.first){
res.sl = res1.sl + res2.sl;
}
res.Max = max(res1.Max,res2.Max);
if(res1.last < res2.first){
res.Max = max(res.Max,res1.sl + res2.pl);
}
}

void build(int rt,int a,int b){
t[rt] = SegTree(a,b);
if(a == b){
int x;
scanf("%d",&x);
t[rt].first = t[rt].last = x;
t[rt].pl = t[rt].sl = t[rt].Max = 1;
return ;
}
int mid = t[rt].mid;
build(lson(rt),a,mid);
build(rson(rt),mid+1,b);
PushUp(rt);
}

void updata(int rt,int index,int val){
if(t[rt].l == t[rt].r){
t[rt].first = t[rt].last = val;
return ;
}
int mid = t[rt].mid;
if(index <= mid)
updata(lson(rt),index,val);
else
updata(rson(rt),index,val);
PushUp(rt);
}

SegTree query(int rt,int a,int b){
if(t[rt].l == a && t[rt].r == b){
return t[rt];
}
int mid = t[rt].mid;
if(b <= mid)
return query(lson(rt),a,b);
else if(a > mid)
return query(rson(rt),a,b);
else{
SegTree res1 = query(lson(rt),a,mid);
SegTree res2 = query(rson(rt),mid+1,b);
SegTree res = SegTree(a,b);
Do(res,res1,res2);
return res;
}
}

int main(){
int n,q,cas;
scanf("%d",&cas);
while(cas--){
scanf("%d%d",&n,&q);
build(1,0,n-1);
while(q--){
char op[5];
scanf("%s",op);
if(op[0] == 'U'){
int index,val;
scanf("%d%d",&index,&val);
updata(1,index,val);
}
else{
int a,b;
scanf("%d%d",&a,&b);
SegTree res = query(1,a,b);
printf("%d\n",res.Max);
}
}
}
return 0;
}