hdu 1754 I Hate It (线段树模板题，炒鸡详细注释版)

  1/* ***********************************************
  2Author :111qqz
  3Created Time :2016年08月18日 星期四 18时40分24秒
  4File Name :code/hdu/1754.cpp
  5************************************************ */
  6#include <cstdio>
  7#include <cstring>
  8#include <iostream>
  9#include <algorithm>
 10#include <vector>
 11#include <queue>
 12#include <stack>
 13#include <set>
 14#include <map>
 15#include <string>
 16#include <cmath>
 17#include <cstdlib>
 18#include <deque>
 19#define fst first
 20#define sec second
 21#define lson l,m,rt<<1
 22#define rson m+1,r,rt<<1|1
 23#define ms(a,x) memset(a,x,sizeof(a))
 24typedef long long LL;
 25#define pi pair < int ,int >
 26#define MP make_pair
 27using namespace std;
 28const double eps = 1E-8;
 29const int dx4[4]={1,0,0,-1};
 30const int dy4[4]={0,-1,1,0};
 31const int inf = 0x3f3f3f3f;
 32const int N=2E5+7;
 33int a[N],n,m;
 34int _max( int x,int y)
 35{
 36    if (x==-1||y==-1)
 37	return x==-1?y:x;
 38    return a[x]>a[y]?x:y;
 39}
 40struct Tree
 41{
 42    Tree *pl,*pr;
 43    int l,r,mx;
 44     void update()
 45    {
 46	mx = _max(pl->mx,pr->mx);
 47    }
 48    Tree(int l,int r) :
 49	    l(l),r(r)
 50	    {
 51		if ( l + 1 == r)
 52		{
 53		    mx = l ;
 54		    return ;
 55		}
 56		pl = new Tree(l,(l+r)>>1);
 57		pr = new Tree((l+r)>>1,r);
 58		update();
 59	    }
 60    void change(int p,int x)
 61    {
 62	if (p < l|| p>=r) return;
 63	if (l+1==r)
 64	{
 65	    a[l] = x;
 66	    return ;
 67	}
 68	pl->change(p,x);
 69	pr->change(p,x);
 70	update();
 71    }
 72    int queryMax(int L,int R)
 73    {
 74	if (L <= l && r <= R) return mx;
 75	if (L>=r || l >=R)
 76	    return -1;
 77	return _max(pl->queryMax(L,R),pr->queryMax(L,R));
 78    }
 79}*rt;
 80int main()
 81{
 82	#ifndef  ONLINE_JUDGE 
 83	freopen("code/in.txt","r",stdin);
 84  #endif
 85    while (~scanf("%d%d",&n,&m))
 86    {
 87	ms(a,0);
 88	for ( int i = 0 ; i < n ; i++) scanf("%d",a+i);
 89	rt = new Tree(0,n);
 90	while (m--)
 91	{
 92	    char opt[3];
 93	    int x,y;
 94	    scanf("%s %d %d",opt,&x,&y);
 95	    x--;
 96	    if (opt[0]=='Q')
 97		printf("%d\n",a[rt->queryMax(x,y)]);
 98	    else rt->change(x,y);
 99	}
100    }
101  #ifndef ONLINE_JUDGE  
102  fclose(stdin);
103  #endif
104    return 0;
105}

 1#include <cstdio>
 2#include <cstring>
 3#include <iostream>
 4#include <algorithm>
 5#include <vector>
 6#include <queue>
 7#include <set>
 8#include <map>
 9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair

 1using namespace std;
 2const double eps = 1E-8;
 3const int dx4[4]={1,0,0,-1};
 4const int dy4[4]={0,-1,1,0};
 5const int inf = 0x3f3f3f3f;
 6const int N=2E5+7;
 7int n,m;
 8int a[N];
 9int MAX[N<<2];//MAX[i]表示的是第i个节点所存储的信息，根据题目会有所变化，这道题存储的是以i节点为根节点的子树的最大值（也就是i节点所表示的区间的最大值）
10void PushUp(int rt)
11{
12    MAX[rt] = max(MAX[rt<<1],MAX[rt<<1|1]);  //线段树上每一个节点代表一段区间，该区间的最大值是把区间分成两部分，每一部分的最大值的最大值，也就是该节点（rt)的两个子节点取最大值。
13}                                           //编号为i节点的两个子节点的编号为i*2和 i*2+1,写成位运算也就是 rt<<1和rt<<1|1（因为左移动一位以后末尾肯定为0，“或”1就相当于+1
14					    //写成位运算是因为不用考虑优先级的问题。。因为加法的优先级比位移高，而或运算的优先级比位移低。
15void update(int p,int sc,int l,int r,int rt) //p表示要更新的的节点的位置，sc表示要更新成什么，l,r,rt三个参数表示当前的树，初始就是整个线段树。
16{
17   // printf("p:%d sc:%d l:%d r:%d rt:%d\n",p,sc,l,r,rt);
18    if (l==r) //此时该区间只有一个数，说明已经到了线段树的底部（叶子节点），一个数的最大值就是本身。直接更新
19    {
20	MAX[rt]= sc;
21	return ;
22    }
23    int m = (l+r)>>1; //单点更新的时候，要更新所有包含该单点的子区间（子树）
24    if (p<=m) update(p,sc,lson);
25    else update(p,sc,rson);

 1    PushUp(rt);//当前区间的子区间更新完成后，可能对当前区间的答案有影响，记得更新（从下往上)
 2}
 3void build(int l,int r,int rt)
 4{
 5 //   printf("l:%d r:%d rt:%d\n",l,r,rt);
 6    if (l==r)
 7    {
 8	scanf("%d",&MAX[rt]);
 9	return;
10    }
11    int m = (l+r)>>1;//当前树的两个子树对应到区间的角度，就是把当前区间分成尽可能相同长度的两部分，m为分界点，前一半区间为[l,m]后一半为[m+1,r].
12    build(lson);
13    build(rson);  //递归建树，建一棵树只需要先建该树的两棵子树，递归的终点是(l==r)，此时到达线段树的叶子节点，对应区间中只有一个数。
14    PushUp(rt);  //当当前树的左右子树都建好，就可以向上更新了。
15}
16int query(int L,int R,int l,int r,int rt) //L,R为当前询问的区间，l,r,rt表示当前的子树,初始是在整棵线段树中查询。
17{
18    if ( L<=l&&r<=R ) //如果当前询问的区间可以完整覆盖当前树的区间，那么这棵子树所代表的区间的最大值就有可能成为当前查询区间的答案，因此直接返回。
19    {
20	return MAX[rt];
21    }
22    int m = (l+r)>>1;  //如果当前询问的区间不能完整覆盖当前树的区间，那么就继续查询当前树的区间的子区间（子树），因为子树表示的区间越来越小，总会完全覆盖。
23    int ret = 0 ;
24    if (L<=m){// 只有当前询问区间和左子树的区间由交点时，左子树对应的区间的答案才会对当前询问的区间有意义。
25	int res = query(L,R,lson);
26	ret = max(ret,res); //答案是所有当前询问区间所能覆盖到的树上的子区间所代表的最大值中的最大值。
27    }
28    if (R>m){//其实是R>=m+1，同理。
29	int res = query(L,R,rson);
30	ret = max(res,ret);
31    }
32    return ret;
33}
34int main()
35{
36	#ifndef  ONLINE_JUDGE 
37	freopen("code/in.txt","r",stdin);
38  #endif

 1	while (~scanf("%d%d",&n,&m))
 2	{
 3	    build(1,n,1);//直接建树的时候读入，根节点为1.
 4	    while(m--)
 5	    {
 6		char opt[10];
 7		int a,b;
 8		scanf("%s%d%d",opt,&a,&b);
 9		if (opt[0]=='Q') printf("%d\n",query(a,b,1,n,1));
10		else update(a,b,1,n,1);
11	    }
12	}

1  #ifndef ONLINE_JUDGE  
2  fclose(stdin);
3  #endif
4    return 0;
5}