线段树主要的优势是在将一个线性的数组转换成一棵树，从而减少大量的重复操作，并且在树中的节点保存一些信息，以便更好的统计！它的各个操作的复杂度都是在logn的，而且我们知道，对于n个节点来说，最多是只有2n-1个树的节点，另外对于一个如果有maxn个节点，那么我们知道最多要用4*maxn个树的节点，这个可以证明
Poj2828 插入队列，在这个过程中，后一个人可能会覆盖前一个人,那么如何用线段树来解呢，我们知道线段树的叶子节点代表的就是当个节点的值，这里，我们把树的节点表示空位的大小，那么在他插入的时候，然后从后面开始插入，那么如果前面出现重复的，那么因为空位数减少了，那么他们也会插在后面,插入的根据是根据空位的大侠来的，这个更新可以这样写
Void update(int p,int l,int r,int rt)
{
当前节点的空位数减少1
如果p此时比他左孩子节点的空位数大，那么在往有孩子插入，此时空位数p-tree[mid].v
否则，遍历左孩子
}
 
1 //AC 用了3532MS
2#include<iostream>
3#include<cstdio>
4#define maxn 200005
5using namespace std;
6struct tree
7 {
8 int lnode,rnode;
9 int v;
10 };
11tree a[maxn*4];
12int res[maxn];
13int pos[maxn],val[maxn];
14int posi;
15void build(int l,int r,int rt)
16{
17 a[rt].v=r-l+1;
18 if(l==r)
19  {
20
21 return ;
22 }
23 int mid=(l+r)>>1;
24 build(l,mid,rt<<1);
25 build(mid+1,r,rt<<1|1);
26}
27void update(int p,int l,int r,int rt)
28{
29 a[rt].v--; //该位置的空位数减少一
30 if(l==r)
31 {
32 posi=l;
33 return ;
34 }
35 int mid=(l+r)>>1;
36 if(p<=a[rt<<1].v) //
37 update(p,l,mid,rt<<1);
38 else
39 update(p-a[rt<<1].v,mid+1,r,rt<<1|1); //这里一定要注意是rt，作为根节点的值
40}
41int main()
42{
43 int n;
44 while(cin>>n)
45 {
46 for(int i=1;i<=n;i++)
47 //cin>>pos[i]>>val[i];
48 scanf("%d%d",&pos[i],&val[i]);
49 build(1,n,1);
50 for(int i=n;i>=1;i--)
51 {
52 update(pos[i]+1,1,n,1);
53 res[posi]=val[i];
54 }
55 for(int i=1;i<=n;i++)
56 {
57 /**//* if(i==1)
58 cout<<res[i];
59 else
60 cout<<" "<<res[i];*/
61 printf("%d%c",res[i],(i==n?'\n':' '));
62 }
63 // cout<<endl;
64 }
65}
66
Hdoj 1754 要求的是一段区间的最大值，这个在更新的时候，要不断更新父子节点，另外在查询的时候，其实对于每一次，最后的来的值总是从叶子节点的来的，只不过利用二分的思想，让他每次都舍弃了一半的选择！
code
1//hdoj 1754
2/**//*
3 经典的线段树问题了
4 在一段区间内实施某个操作，然后在查询，用线段树可以高效的解决
5 线段树，可以设置这样几个信息，其中一个保存的是一段区间的最大值，
6 在更新的过程中，逐次更新
7*/
8#include<iostream>
9#define maxn 20005
10using namespace std;
11struct Tree
12{
13 int lnode,rnode,maxscore;
14};
15Tree tree[maxn*4];
16int a[maxn];
17int max1;
18void build(int l,int r,int rt,int pos,int p)
19{
20 // tree[rt].lnode=l;tree[rt].rnode=r;
21 if(l==r)
22 {
23 tree[rt].maxscore=p;
24 return ;
25 }
26 int mid=(l+r)>>1;
27 if(pos<=mid)
28 build(l,mid,rt<<1,pos,p);
29 else
30 build(mid+1,r,rt<<1|1,pos,p);
31 tree[rt].maxscore=max(tree[rt>>1].maxscore,tree[rt<<1|1].maxscore);
32}
33void update(int l,int r,int rt,int pos,int p)
34{
35 if(l==r) {tree[rt].maxscore=p;return ;}
36 int mid=(l+r)>>1;
37 if(pos<=mid)
38 update(l,mid,rt<<1,pos,p);
39 else
40 update(mid+1,r,rt<<1|1,pos,p);
41 tree[rt].maxscore=max(tree[rt>>1].maxscore,tree[rt<<1|1].maxscore);
42}
43int query(int L,int R,int l,int r,int rt)
44{
45 //询问这个区间内的最高分数
46
47 if(L<=l&&R>=r)
48 {
49 //说明访问此时已经结束
50 return tree[rt].maxscore;
51 // return max1;
52 }
53 else
54 {
55 int mid=(l+r)>>1;
56 int _lmax=0,_rmax=0;
57 if(L<=mid)
58 _lmax=query(L,R,l,mid,rt<<1);
59 //_lmax=max(_lmax,query(L,R,1,mid,rt<<1));
60 else
61 _rmax=query(L,R,mid+1,r,rt<<1|1);
62 max1=max(_lmax,_rmax);
63 // _lmax=max(_lmax,query(L,R,mid+1,r,rt<<1|1));
64 // return _lmax;
65 }
66 // return _lmax;
67 return max1;
68}
69int main()
70{
71 int num_node,num_query;
72 while(cin>>num_node>>num_query)
73 {
74 //build(1,n,1)
75 //memset(tree,0,sizeof(tree));
76 for(int i=1;i<=num_node;i++)
77 { cin>>a[i];
78 build(1,num_node,1,i,a[i]);
79 }
80
81 for(int i=1;i<=num_query;i++)
82 {
83 char ch;
84 int a,b;
85 cin>>ch>>a>>b;
86 if(ch=='Q')
87 {
88 query(a,b,1,num_node,1);
89 cout<<max1<<endl;
90 }
91 else if(ch=='U')
92 {
93 update(1,num_node,1,a,b);
94 }
95 }
96 }
97}
98
Hdoj1698 hook,这题是用了懒惰标记，要求的问题是在一段区间了进行了某一个操作，然后求整个操作后，总共的和是多少
懒惰的标记是指如果在更新的过程中，父子节点已经被全部覆盖，那么作为他的孩子节点也坐上同样的标记，这个思想是可以用这样，首先判断当前节点有没被完全覆盖，若是，则进行懒惰标记，对于他的所有孩子节点都是如此
code
1//初次有一个错误 ,用cin时 超了，用scanf就花了 1000ms
2#include<iostream>
3using namespace std;
4#define maxn 100005
5#define lp(x) (x<<1)
6#define rp(x) (x<<1|1)
7int lazy[maxn<<2];
8int stick[maxn<<2];
9void pushUp(int rt)
10{
11 stick[rt]=stick[lp(rt)]+stick[rp(rt)];
12}
13void pushDown(int p,int len)
14{
15 //这个就是懒惰标记，思想就是要更新的节点已经被 当前的节点覆盖，那么不需要往下继续覆盖，
16 //在当前节点记录下信息，
17 if(lazy[p])
18 {
19 lazy[lp(p)]=lazy[rp(p)]=lazy[p];
20 //更新信息
21 stick[lp(p)]=(len-(len>>1))*lazy[lp(p)];
22 stick[rp(p)]=(len>>1)*lazy[rp(p)];
23 lazy[p]=0; //这里就不太明白了，也就是说在更新好此时的节点后，那么把它又标记成0，表示应经算过这一段
24 }
25}
26void build(int l,int r,int rt)
27{
28 //如何建造呢
29 lazy[rt]=0;
30 if(l==r) //说明到了根节点
31 {
32 stick[rt]=1;
33 return ;
34 }
35 int mid=(l+r)>>1;
36 build(l,mid,lp(rt));
37 build(mid+1,r,rp(rt));
38 pushUp(rt);
39}
40void update(int L,int R,int z,int l,int r,int rt)
41{
42
43 if(L<=l&&R>=r)
44 {
45 lazy[rt]=z;
46 stick[rt]=(r-l+1)*z;
47 return ; //这里如果不返回，那么就是错误 (1)
48 }
49 pushDown(rt,(r-l+1));
50 int mid=(l+r)>>1;
51 if(L<=mid) update(L,R,z,l,mid,lp(rt));
52 if(R>mid) update(L,R,z,mid+1,r,rp(rt));
53 pushUp(rt);
54}
55
56int main()
57{
58 int T,n,Q;
59 int x,y,z;
60 // cin>>T;
61 scanf("%d",&T);
62 int k=0;
63 while(T--)
64 {
65
66 // cin>>n>>Q;
67 scanf("%d%d",&n,&Q);
68 build(1,n,1);
69 for(int i=1;i<=Q;i++)
70 {
71
72 //cin>>x>>y>>z;
73 scanf("%d%d%d",&x,&y,&z);
74 update(x,y,z,1,n,1);
75 }
76
77 //cout<<stick[1]<<endl;
78 printf("Case %d: The total value of the hook is %d.\n",++k,stick[1]);
79 }
80 system("pause");
81}
82
Hdoj 3577这题的大意就是 火车有k个座位，乘客可以买从a到b的车票，给你一些乘客的买票需求，要你求的就是哪些乘客能够买到票
这题用的是线段树，我们知道最好的情况是在每一条路线上能够充分的用上，也就是被完全覆盖，那么在判段许可的时候，如果此段已经被覆盖过，那么不行！这里有一个问
题就是，因为有多个座位，所以每个座位都有一条路线，然后按照上述的思想进行处理即可
问题：第一次wa，是因为这里没注意更新的区间应该是[a,b-1],因为我到了b站之后，就从这站下来了，然后下一次是可以从b站出发的
code
1//406MS
2#include<iostream>
3#include<algorithm>
4#define maxn 1000010
5#define lp(x) (x<<1)
6#define rp(x) (x<<1|1)
7using namespace std;
8int lazy[maxn<<2];
9int stick[maxn<<2];
10//int sum[maxn];
11int res[100010];
12int max(int a,int b)
13{
14 return a>b?a:b;
15}
16void pushUp(int rt)
17{
18 stick[rt]=max(stick[lp(rt)],stick[rp(rt)]); //这里也要注意了，随着题目变化，模板也要变化，不是求和
19}
20void pushDown(int p)
21{
22 //这个就是懒惰标记，思想就是要更新的节点已经被 当前的节点覆盖，那么不需要往下继续覆盖，
23 //在当前节点记录下信息，lazy[p]标记的是当前被覆盖的次数
24 if(lazy[p])
25 {
26 // lazy[lp(p)]=lazy[rp(p)]=lazy[p];
27 //更新信息
28 stick[lp(p)]+=lazy[p]; //表示加上这些覆盖的次数的值
29 stick[rp(p)]+=lazy[p];
30 lazy[lp(p)]+=lazy[p];
31 lazy[rp(p)]+=lazy[p];
32 lazy[p]=0;
33 }
34}
35void update(int L,int R,int z,int l,int r,int rt)
36{
37 if(L<=l&&R>=r)
38 {
39 lazy[rt]+=z;
40 stick[rt]+=z;
41 return ; //这里如果不返回，那么就是错误 (1)
42 }
43 pushDown(rt);
44 int mid=(l+r)>>1;
45 if(L<=mid) update(L,R,z,l,mid,lp(rt));
46 if(R>mid) update(L,R,z,mid+1,r,rp(rt));
47 pushUp(rt);
48}
49int query(int L,int R,int l,int r,int rt)
50{
51 if(L<=l&&R>=r)
52 {
53 return stick[rt];
54 }
55 pushDown(rt);
56 int ret=0;
57 int mid=(l+r)>>1;
58 if(L<=mid) ret=max(ret,query(L,R,l,mid,lp(rt)));
59 if(R>mid) ret=max(ret,query(L,R,mid+1,r,rp(rt)));
60 //pushUp(rt); //这里不能用pushUp
61 return ret; //这里能够保证最后的ret就是我们要的ret
62}
63int main()
64{
65 int t;
66 int k,Q,a,b;
67 int nCase=0;
68 cin>>t;
69 while(t--)
70 {
71 cin>>k>>Q;
72 memset(stick,0,sizeof(stick));
73 memset(lazy,0,sizeof(lazy));
74 int cnt=0;
75 for(int i=1;i<=Q;i++)
76 {
77 cin>>a>>b;
78 b--; //这里要注意了更新的区间应该是[a,b-1],因为我到了b站之后，就从这站下来了，然后下一次是可以从b站出发的
79 if(query(a,b,1,1000002,1)<k) //最多是已经覆盖k-1条
80 {
81 res[cnt++]=i;
82 update(a,b,1,1,1000002,1);
83 }
84 }
85 printf("Case %d:\n",++nCase);
86 for(int i=0;i<cnt;i++)
87 printf("%d ",res[i]);
88 printf("\n\n");
89 }
90 system("pause");
91}
92
Poj2528 这一题就是一些海报，要求的是最后没有被完全覆盖的海报总数， 那么怎么求呢，一个问题就是如果我们按照从一开始的数据进行处理的话，那么前一张海报可能会被后一张海报完全覆盖，那么最后的结果就无法有效求出，那么我们可以反过来，那就是从最上面的海报开始，那么判断这段区间内是否已经被完全覆盖过，若是，则不用加1，否则加1
这题先用离散化，将大的数据映射到比较小的数字上面，然后，根据离散后的数据我们可以得出，现在的问题就是，如何求，才能够去掉被完全覆盖的区间，那么这里我们建立一个hash，这个hash存放的值是表示第i个海报，如果查询的当前的节点的记录值，在hash表里没有被记录过，那么说明此区间没有被完全覆盖，
现在证明这样做的正确性，首先如果前一张海报被后一张覆盖的情况，那么由于更新后的cnt[]的域记录的也是后一张海报的离散化值，那么就不会记录错误
总结上面的过程，这个题目的总体思路就是输入数据后，离散处理，在针对每一个进行更新，最后查询，代码待更新。。
|