Poj2828 插入隊(duì)列，在這個(gè)過(guò)程中，后一個(gè)人可能會(huì)覆蓋前一個(gè)人,那么如何用線段樹(shù)來(lái)解呢，我們知道線段樹(shù)的葉子節(jié)點(diǎn)代表的就是當(dāng)個(gè)節(jié)點(diǎn)的值，這里，我們把樹(shù)的節(jié)點(diǎn)表示空位的大小，那么在他插入的時(shí)候，然后從后面開(kāi)始插入，那么如果前面出現(xiàn)重復(fù)的，那么因?yàn)榭瘴粩?shù)減少了，那么他們也會(huì)插在后面,插入的根據(jù)是根據(jù)空位的大俠來(lái)的，這個(gè)更新可以這樣寫(xiě)

 Void update(int p,int l,int r,int rt)

{

  當(dāng)前節(jié)點(diǎn)的空位數(shù)減少1

  如果p此時(shí)比他左孩子節(jié)點(diǎn)的空位數(shù)大，那么在往有孩子插入，此時(shí)空位數(shù)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--;  //該位置的空位數(shù)減少一 
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，作為根節(jié)點(diǎn)的值 
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 要求的是一段區(qū)間的最大值，這個(gè)在更新的時(shí)候，要不斷更新父子節(jié)點(diǎn)，另外在查詢的時(shí)候，其實(shí)對(duì)于每一次，最后的來(lái)的值總是從葉子節(jié)點(diǎn)的來(lái)的，只不過(guò)利用二分的思想，讓他每次都舍棄了一半的選擇！

code
 1//hdoj 1754 
 2/**//*
 3  經(jīng)典的線段樹(shù)問(wèn)題了
 4  在一段區(qū)間內(nèi)實(shí)施某個(gè)操作，然后在查詢，用線段樹(shù)可以高效的解決
 5   線段樹(shù)，可以設(shè)置這樣幾個(gè)信息，其中一個(gè)保存的是一段區(qū)間的最大值，
 6   在更新的過(guò)程中，逐次更新 
 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  //詢問(wèn)這個(gè)區(qū)間內(nèi)的最高分?jǐn)?shù)
46 
47  if(L<=l&&R>=r)
48   {
49     //說(shuō)明訪問(wèn)此時(shí)已經(jīng)結(jié)束 
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,這題是用了懶惰標(biāo)記，要求的問(wèn)題是在一段區(qū)間了進(jìn)行了某一個(gè)操作，然后求整個(gè)操作后，總共的和是多少

 懶惰的標(biāo)記是指如果在更新的過(guò)程中，父子節(jié)點(diǎn)已經(jīng)被全部覆蓋，那么作為他的孩子節(jié)點(diǎn)也坐上同樣的標(biāo)記，這個(gè)思想是可以用這樣，首先判斷當(dāng)前節(jié)點(diǎn)有沒(méi)被完全覆蓋，若是，則進(jìn)行懶惰標(biāo)記，對(duì)于他的所有孩子節(jié)點(diǎn)都是如此

code
 1//初次有一個(gè)錯(cuò)誤 ,用cin時(shí) 超了，用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     //這個(gè)就是懶惰標(biāo)記，思想就是要更新的節(jié)點(diǎn)已經(jīng)被 當(dāng)前的節(jié)點(diǎn)覆蓋，那么不需要往下繼續(xù)覆蓋，
16     //在當(dāng)前節(jié)點(diǎn)記錄下信息，
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;   //這里就不太明白了，也就是說(shuō)在更新好此時(shí)的節(jié)點(diǎn)后，那么把它又標(biāo)記成0，表示應(yīng)經(jīng)算過(guò)這一段 
24     } 
25} 
26void build(int l,int r,int rt)
27{
28  //如何建造呢
29  lazy[rt]=0;
30  if(l==r)  //說(shuō)明到了根節(jié)點(diǎn)
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 ;    //這里如果不返回，那么就是錯(cuò)誤 (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這題的大意就是 火車(chē)有k個(gè)座位，乘客可以買(mǎi)從a到b的車(chē)票，給你一些乘客的買(mǎi)票需求，要你求的就是哪些乘客能夠買(mǎi)到票 

  這題用的是線段樹(shù)，我們知道最好的情況是在每一條路線上能夠充分的用上，也就是被完全覆蓋，那么在判段許可的時(shí)候，如果此段已經(jīng)被覆蓋過(guò)，那么不行！這里有一個(gè)問(wèn)

題就是，因?yàn)橛卸鄠€(gè)座位，所以每個(gè)座位都有一條路線，然后按照上述的思想進(jìn)行處理即可

問(wèn)題：第一次wa，是因?yàn)檫@里沒(méi)注意更新的區(qū)間應(yīng)該是[a,b-1],因?yàn)槲业搅?/font>b站之后，就從這站下來(lái)了，然后下一次是可以從b站出發(fā)的 

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     //這個(gè)就是懶惰標(biāo)記，思想就是要更新的節(jié)點(diǎn)已經(jīng)被 當(dāng)前的節(jié)點(diǎn)覆蓋，那么不需要往下繼續(xù)覆蓋，
23     //在當(dāng)前節(jié)點(diǎn)記錄下信息，lazy[p]標(biāo)記的是當(dāng)前被覆蓋的次數(shù) 
24     if(lazy[p])
25     {
26      // lazy[lp(p)]=lazy[rp(p)]=lazy[p]; 
27       //更新信息 
28       stick[lp(p)]+=lazy[p];  //表示加上這些覆蓋的次數(shù)的值 
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 ;    //這里如果不返回，那么就是錯(cuò)誤 (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--;             //這里要注意了更新的區(qū)間應(yīng)該是[a,b-1],因?yàn)槲业搅薭站之后，就從這站下來(lái)了，然后下一次是可以從b站出發(fā)的 
79       if(query(a,b,1,1000002,1)<k)  //最多是已經(jīng)覆蓋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 這一題就是一些海報(bào)，要求的是最后沒(méi)有被完全覆蓋的海報(bào)總數(shù)， 那么怎么求呢，一個(gè)問(wèn)題就是如果我們按照從一開(kāi)始的數(shù)據(jù)進(jìn)行處理的話，那么前一張海報(bào)可能會(huì)被后一張海報(bào)完全覆蓋，那么最后的結(jié)果就無(wú)法有效求出，那么我們可以反過(guò)來(lái)，那就是從最上面的海報(bào)開(kāi)始，那么判斷這段區(qū)間內(nèi)是否已經(jīng)被完全覆蓋過(guò)，若是，則不用加1，否則加1

 這題先用離散化，將大的數(shù)據(jù)映射到比較小的數(shù)字上面，然后，根據(jù)離散后的數(shù)據(jù)我們可以得出，現(xiàn)在的問(wèn)題就是，如何求，才能夠去掉被完全覆蓋的區(qū)間，那么這里我們建立一個(gè)hash，這個(gè)hash存放的值是表示第i個(gè)海報(bào)，如果查詢的當(dāng)前的節(jié)點(diǎn)的記錄值，在hash表里沒(méi)有被記錄過(guò)，那么說(shuō)明此區(qū)間沒(méi)有被完全覆蓋，

 現(xiàn)在證明這樣做的正確性，首先如果前一張海報(bào)被后一張覆蓋的情況，那么由于更新后的cnt[]的域記錄的也是后一張海報(bào)的離散化值，那么就不會(huì)記錄錯(cuò)誤

  總結(jié)上面的過(guò)程，這個(gè)題目的總體思路就是輸入數(shù)據(jù)后，離散處理，在針對(duì)每一個(gè)進(jìn)行更新，最后查詢，代碼待更新。。