HDU 4614線分ツリー+二分

最初は自分の方法で、ずっとWAをして、自分でも间违いの例を出すことができなくて、自分のコードを放弃して、他の人の方法を见てすべて线分の木+二分で、论理はとてもはっきりしていて、とても书きやすくて、基本は板です.

#include 
#include 
#include 
#include 
using namespace std;
struct node
{
    int sum,lz;
}a[50005 << 3];
void build(int d, int l, int r)
{
    a[d].sum = r - l + 1; a[d].lz = -1;
    if(l == r) return;
    int m = (l+r) >> 1;
    build(d*2,l,m); build(d*2+1,m+1,r);
}
void pushup(int d)
{
    a[d].sum = a[d*2].sum + a[d*2 + 1].sum;
}
void pushdown(int d, int l, int r)
{
    if(a[d].lz != -1)
    {
        int m = (l+r) >> 1;
        int ld = d*2, rd = ld + 1;
        a[ld].lz = a[rd].lz = a[d].lz;
        a[ld].sum = (m - l + 1)*a[d].lz;
        a[rd].sum = (r - m)*a[d].lz;
        a[d].lz = -1;
    }
}
int query(int d, int l, int r, int ql, int qr)
{
    if(ql <= l && r <= qr)
    {
        return a[d].sum;
    }
    int m = (l+r) >> 1;
    int ans = 0;
    pushdown(d,l,r);
    if(ql <= m) ans += query(d*2,l,m,ql,qr);
    if(m < qr) ans += query(d*2+1,m+1,r,ql,qr);
    return ans;
}
int query_0(int d, int l, int r, int ql, int qr)
{
    if(ql <= l && r <= qr)
    {
        return r - l +1  - a[d].sum;
    }
    int m = (l+r) >> 1; int ans = 0;
    pushdown(d,l,r);
    if(ql <= m) ans += query_0(d*2,l,m,ql,qr);
    if(m < qr) ans += query_0(d*2+1,m+1,r,ql,qr);
    return ans;
}
void update(int d, int l, int r, int ql, int qr, int c)
{
    if(ql <= l && r <= qr)
    {
        a[d].lz = c;
        a[d].sum = (r - l + 1)*c;
        return;
    }
    pushdown(d,l,r);
    int m = (l +r) >> 1;
    if(ql <= m) update(d*2,l,m,ql,qr,c);
    if(m < qr)update(d*2+1,m+1,r,ql,qr,c);
    pushup(d);
    return;
}
int main()
{
    int n,m;
    int times; cin >> times;
    while(times --)
    {
        scanf("%d%d",&n,&m);
        build(1,1,n);
        while(m -- )
        {
            int k,x,y;
            scanf("%d%d%d",&k,&x,&y);
            if(k == 1)
            {
                int t = query(1,1,n,x+1,n);
                if(t == 0)
                {
                    printf("Can not put any one.
");
                    continue;
                }
                int lsum = 0;
                if(x != 0)
                lsum = query(1,1,n,1,x);
                lsum ++;
                //cout <> 1;
                    nows = query(1,1,n,l,m);
                    //cout << l << "    " <= lsum) r = m;
                    else if(nows < lsum)
                    {
                         lsum -= nows;
                         l = m + 1;
                    }
                }
                lp = l;
                int rsum = min(y,t); l = lp,r = n;
                  while(l < r)
                {
                    m = (l+r) >> 1;
                    nows = query(1,1,n,l,m);
                   // cout << l <= rsum) r = m;
                    else if(nows < rsum)
                    {
                         rsum -= nows;
                         l = m + 1;
                    }
                }
                int rp = l;
                printf("%d %d
",lp- 1,rp-1);
                update(1,1,n,lp,rp,0);
            }
            else
            {
                printf("%d
",query_0(1,1,n,x+1,y+1));
                update(1,1,n,x+1,y+1,1);
            }
        }
        printf("
");
    }
}

————————————————————————————————————————————————————————————分割線
ついでにWAのコードを贴って、どこが间违っていることを探し出せませんでした

#include 
#include 
#include 
#include 
#pragma comment(linker, "/STACK:36777216")
using namespace std;
struct node
{
    int sum,st,en;
    int lz;
}a[50010<<4];
void build(int d,int l, int r)
{
   int len = r - l + 1;
   a[d].sum = len; a[d].st = l,a[d].en = r;
   a[d].lz = -1;
   if(l == r)  return;
   int m = (l+r)>>1;
   build(d*2,l,m);
   build(d*2+1,m+1,r);
   return;
}

void pushup(int d)
{
    int ld = d*2,rd = d*2 +1;
    a[d].sum = a[ld].sum + a[rd].sum;
    if(a[d].sum == 0) return;
    if(a[ld].sum != 0) a[d].st = a[ld].st;
    else a[d].st = a[rd].st;
    if(a[rd].sum != 0) a[d].en = a[rd].en;
    else a[d].en = a[ld].en;
    return ;
}
void push1(int d, int l, int r)
{
     if(a[d].sum == r - l +1 && a[d].lz == 0)
     {
         int ld = 2*d, rd = 2*d + 1;
         int m = (l+r)>>1;
         a[ld].sum = m - l +1; a[rd].sum = r - m;
         a[ld].st = l, a[ld].en = m;
         a[rd].st = m+1, a[rd].en = r;
         a[d].lz = -1;
         a[ld].lz = 0, a[rd].lz = 0;
     }
     return;
}
int al,ar,s,ts;
void pushdown(int d , int l, int r)
{
    
    //cout << l << " pp    " <> 1;int ld = d*2, rd = ld + 1;
     if(a[ld].sum && s)pushdown(ld,l,m);
     if(a[rd].sum && s)pushdown(rd,m+1,r);
     pushup(d);
    }
}
void push0(int d, int l, int r)
{
    if(a[d].sum == 0 && a[d].lz == 1)
    {
         a[d].lz = -1;
         int ld = 2*d, rd = 2*d + 1;
         int m = (l+r)>>1;
         a[ld].sum = 0; a[rd].sum = 0;
         a[ld].lz = 1; a[rd].lz = 1;
    }
}
void query(int d, int l, int r, int t)
{
    if(l  == t)
    {
    //cout << l < s)
        {
            if(s == ts) al = a[d].st;
            pushdown(d,l,r);
        }
        else if(a[d].sum <= s)
        {
            if(s== ts) al = a[d].st;
            s -= a[d].sum; ar = a[d].en; a[d].lz = 1;
            a[d].sum = 0;
        }
        return ;
    }

    push1(d,l,r);
    int m = (l+r) >>1;
    //cout << l << "     " << r < 0 && a[d*2+1].sum) query(d*2+1,m+1,r,max(t,m+1));
    pushup(d);
}
int update(int d, int l, int r ,int ql, int qr)
{
    int ans = 0;
    if(ql <= l && r <= qr)
    {
        ans =r - l+ 1 -  a[d].sum;
        //cout << l <>1;
    if(ql <= m) ans += update(d*2,l,m,ql,qr);
    if(m < qr) ans += update(d*2+1,m+1,r,ql,qr);
    pushup(d);
    return ans;
}
int main()
{
    int times,n,m,op;
    scanf("%d",×);
    while(times --)
    {
        int x,y;
        scanf("%d%d",&n,&m);
        build(1,1,n);
        while(m --)
        {
            scanf("%d%d%d",&op,&x,&y);
            if(op == 1)
            {
                s = y;ts = y; x += 1;
              //  cout << n <