HDU4614[線段樹。]

果然看了理解了一下大牛的代碼然後自己敲結果果然有不少錯誤

回復說，線段樹做為一種數據結構，最好以一種風格過一題裸的然後作為自己的模板。。

二分寫的也很惡心哪

還有題目稍復雜一點的注定得推敲各種公式，不光DP注意邊界那樣令自己惡心，就是這些公式+1，-1結果都是差之千裡，或者自己根本調試不出來。

思路很重要，模板也比較重要，線段樹裸敲的話容易出錯，比樹狀數組出錯幾率大的多。
 

 
#include <cstdio>   
#include <cstdlib>   
#include <cstring>   
#include <cstring>   
#include <cmath>   
#include <ctime>   
#include <iostream>   
#include <algorithm>   
#include <string>   
#include <queue>   
#include <set>   
#include <map>   
#include <vector>   
#include <assert.h>   
  
using namespace std;  
  
#define lowbit(i) (i&-i)   
#define sqr(x) ((x)*(x))   
#define enter printf("\n")   
#define is_sqr(x) (x&(x-1))   
#define pi acos(-1.0)   
#define clr(x)  memset(x,0,sizeof(x))   
#define fp1 freopen("in.txt","r",stdin)   
#define fp2 freopen("out.txt","w",stdout)   
#define pb push_back   
  
typedef long long LL;  
  
const double eps = 1e-7;  
const double DINF = 1e100;  
const int INF = 1000000006;  
const LL LINF = 1000000000000000005ll;  
const int MOD = (int) 1e9 + 7;  
const int maxn=300005;  
  
template<class T> inline T Min(T a,T b){return a<b?a:b;}  
template<class T> inline T Max(T a,T b){return a>b?a:b;}  
template<class T> inline T Min(T a,T b,T c){return min(min(a, b),c);}  
template<class T> inline T Max(T a,T b,T c){return max(max(a, b),c);}  
  
struct Node  
{  
    int l,r,sum,add;  
}node[maxn];//這地方也有技巧 線段樹要存多大的數據 比如樹高為H   
void build(int root,int l,int r)  
{  
    node[root].l=l;  
    node[root].r=r;  
    node[root].add=-1;  
    node[root].sum=0;  
    if(node[root].l==node[root].r) return ;  
    else  
    {  
       int mid=(l+r)/2;  
       build(root*2,l,mid);  
       build(root*2+1,mid+1,r);  
    }  
}  
int query(int root,int l,int r)  
{  
    if(node[root].l==l&&node[root].r==r) return node[root].sum;//又有錯誤   
    if(node[root].add>=0)//更新子結點？   
    {  
       int ls=root*2,rs=root*2+1;  
       //node[root].sum=(node[root].r-node[root].l+1)*node[root].add;   
       //這一步不需要，前面已修改   
       node[ls].sum=(node[ls].r-node[ls].l+1)*node[root].add;//兩處錯誤   
       node[rs].sum=(node[rs].r-node[rs].l+1)*node[root].add;// ls rs用不用更新？   
       node[ls].add=node[rs].add=node[root].add;  
       node[root].add=-1;  
    }  
    int ans=0;  
    int mid=(node[root].l+node[root].r)/2;  
    if(r<=mid)  
    {  
        return query(root*2,l,r);  
    }  
    else if(l>mid)  
    {  
        return query(root*2+1,l,r);  
    }  
    else  
    {  
        ans=query(root*2,l,mid);  
        ans+=query(root*2+1,mid+1,r);  
    }  
    return ans;  
}  
void update(int root,int l,int r,int add)  
{  
    if(node[root].l==l&&node[root].r==r)//不夠掌握的就是他這塊的更新和上面的什麼關系   
    {  
        node[root].add=add;  
        node[root].sum=(node[root].r-node[root].l+1)*node[root].add;  
        return;  
    }  
    int mid=(node[root].l+node[root].r)/2;  
    if(r<=mid)  
    {  
        update(root*2,l,r,add);  
    }  
    else if(l>mid)  
    {  
        update(root*2+1,l,r,add);  
    }  
    else  
    {  
        update(root*2,l,mid,add);  
        update(root*2+1,mid+1,r,add);  
    }  
    node[root].sum=node[root*2].sum+node[root*2+1].sum;  
}  
int bin_sea(int l,int r,int a)  
{  
    int ll=l;  
    while(l<r)  
    {  
      int mid=(l+r)/2;  
      int temp_num=query(1,ll,mid);  
      if(mid-ll+1-temp_num>=a)//最開始沒寫出二分查找來 後來又因為mid-l+1錯了 //第N處錯誤 //第N+1處錯誤   
         r=mid;  
      else l=mid+1;  
    }  
    return l;  
}  
int main()  
{  
    int ncase;  
    scanf("%d",&ncase);  
    while(ncase--)  
    {  
        int n,m,i,j;  
        scanf("%d%d",&n,&m);  
        n--;  
        build(1,0,n);  
        for(i=1;i<=m;i++)  
        {  
            int a,b,c;  
            scanf("%d%d%d",&a,&b,&c);  
            if(a==1)  
            {  
                int right_num=query(1,b,n);  
               // printf("~%d\n",right_num);   
                if(right_num==n-b+1)  
                    printf("Can not put any one.\n");  
                else  
                {  
                    int left_num=b==0?0:query(1,0,b-1);//這地方要是b==0的話 left_num直接等於0 （注意點1）//第N+3處錯誤   
                    //printf("~%d\n",left_num);   
                    int left_pos=bin_sea(0,n,b-left_num+1);//為嗎是b-left_num+1？而不是+2   
                    int right_pos=bin_sea(b,n,min(n-b+1-right_num,c));//（注意點2，min）   
                    printf("%d %d\n",left_pos,right_pos);  
                    update(1,left_pos,right_pos,1);  
                }  
            }  
            else if(a==2)  
            {  
               printf("%d\n",query(1,b,c));  
               update(1,b,c,0);  
            }  
        }  
        printf("\n");  
    }  
    return 0;  
}  

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <assert.h>

using namespace std;

#define lowbit(i) (i&-i)
#define sqr(x) ((x)*(x))
#define enter printf("\n")
#define is_sqr(x) (x&(x-1))
#define pi acos(-1.0)
#define clr(x)  memset(x,0,sizeof(x))
#define fp1 freopen("in.txt","r",stdin)
#define fp2 freopen("out.txt","w",stdout)
#define pb push_back

typedef long long LL;

const double eps = 1e-7;
const double DINF = 1e100;
const int INF = 1000000006;
const LL LINF = 1000000000000000005ll;
const int MOD = (int) 1e9 + 7;
const int maxn=300005;

template<class T> inline T Min(T a,T b){return a<b?a:b;}
template<class T> inline T Max(T a,T b){return a>b?a:b;}
template<class T> inline T Min(T a,T b,T c){return min(min(a, b),c);}
template<class T> inline T Max(T a,T b,T c){return max(max(a, b),c);}

struct Node
{
    int l,r,sum,add;
}node[maxn];//這地方也有技巧 線段樹要存多大的數據 比如樹高為H
void build(int root,int l,int r)
{
    node[root].l=l;
    node[root].r=r;
    node[root].add=-1;
    node[root].sum=0;
    if(node[root].l==node[root].r) return ;
    else
    {
       int mid=(l+r)/2;
       build(root*2,l,mid);
       build(root*2+1,mid+1,r);
    }
}
int query(int root,int l,int r)
{
    if(node[root].l==l&&node[root].r==r) return node[root].sum;//又有錯誤
    if(node[root].add>=0)//更新子結點？
    {
       int ls=root*2,rs=root*2+1;
       //node[root].sum=(node[root].r-node[root].l+1)*node[root].add;
       //這一步不需要，前面已修改
       node[ls].sum=(node[ls].r-node[ls].l+1)*node[root].add;//兩處錯誤
       node[rs].sum=(node[rs].r-node[rs].l+1)*node[root].add;// ls rs用不用更新？
       node[ls].add=node[rs].add=node[root].add;
       node[root].add=-1;
    }
    int ans=0;
    int mid=(node[root].l+node[root].r)/2;
    if(r<=mid)
    {
        return query(root*2,l,r);
    }
    else if(l>mid)
    {
        return query(root*2+1,l,r);
    }
    else
    {
        ans=query(root*2,l,mid);
        ans+=query(root*2+1,mid+1,r);
    }
    return ans;
}
void update(int root,int l,int r,int add)
{
    if(node[root].l==l&&node[root].r==r)//不夠掌握的就是他這塊的更新和上面的什麼關系
    {
        node[root].add=add;
        node[root].sum=(node[root].r-node[root].l+1)*node[root].add;
        return;
    }
    int mid=(node[root].l+node[root].r)/2;
    if(r<=mid)
    {
        update(root*2,l,r,add);
    }
    else if(l>mid)
    {
        update(root*2+1,l,r,add);
    }
    else
    {
        update(root*2,l,mid,add);
        update(root*2+1,mid+1,r,add);
    }
    node[root].sum=node[root*2].sum+node[root*2+1].sum;
}
int bin_sea(int l,int r,int a)
{
    int ll=l;
    while(l<r)
    {
      int mid=(l+r)/2;
      int temp_num=query(1,ll,mid);
      if(mid-ll+1-temp_num>=a)//最開始沒寫出二分查找來 後來又因為mid-l+1錯了 //第N處錯誤 //第N+1處錯誤
         r=mid;
      else l=mid+1;
    }
    return l;
}
int main()
{
    int ncase;
    scanf("%d",&ncase);
    while(ncase--)
    {
        int n,m,i,j;
        scanf("%d%d",&n,&m);
        n--;
        build(1,0,n);
        for(i=1;i<=m;i++)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            if(a==1)
            {
                int right_num=query(1,b,n);
               // printf("~%d\n",right_num);
                if(right_num==n-b+1)
                    printf("Can not put any one.\n");
                else
                {
                    int left_num=b==0?0:query(1,0,b-1);//這地方要是b==0的話 left_num直接等於0 （注意點1）//第N+3處錯誤
                    //printf("~%d\n",left_num);
                    int left_pos=bin_sea(0,n,b-left_num+1);//為嗎是b-left_num+1？而不是+2
                    int right_pos=bin_sea(b,n,min(n-b+1-right_num,c));//（注意點2，min）
                    printf("%d %d\n",left_pos,right_pos);
                    update(1,left_pos,right_pos,1);
                }
            }
            else if(a==2)
            {
               printf("%d\n",query(1,b,c));
               update(1,b,c,0);
            }
        }
        printf("\n");
    }
    return 0;
}