C86 树状数组+二分 P2161 [SHOI2009] 会场预约

// 树状数组+二分 O(n*logn*logn)
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int s[N],ed[N];
void change(int x, int k) {for(; x<=N; x+=x&-x)s[x]+=k;}
int sum(int x) {int t=0;for(; x>=1; x-=x&-x)t+=s[x];return t;}
int main() 
{
    int n;scanf("%d", &n);
    memset(s, 0, sizeof(s));
    for(int i=1, tot=0; i<=n; i++) 
    {
        char c;scanf(" %c", &c);
        if(c=='A') 
        {
            int L, R, cnt=0;
            scanf("%d%d", &L, &R);
            while(1) 
            {
                int l=1, r=R, p;//二分找重叠区的起点
                while(l<=r)
                {
                    int mid=(l+r)>>1;
                    if(sum(mid)==sum(R))r=mid-1, p=mid;
                    else  l=mid+1; 
                }

                if(ed[p]>=L) //有重叠则删除
                {  
                    change(p, -1); //区间[p,N]-1
                    ed[p]=0;
                    cnt++;        //重叠区间数+1
                    tot--;        //总区间数-1
                } else break;     //无重叠则退出
            }
            printf("%d\n", cnt);
            change(L, 1); //区间[L,N]+1
            ed[L]=R;     //存区间[L,R]
            tot++;       //总区间数+1
        }
        else printf("%d\n", tot);
    }
    return 0;
}

C86 树状数组+二分 P2161 [SHOI2009] 会场预约

// 树状数组+二分 O(n*logn*logn)
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int s[N],ed[N];
void change(int x,int k) {for(; x<=N; x+=x&-x)s[x]+=k;}
int sum(int x) {int t=0;for(; x>=1; x-=x&-x)t+=s[x];return t;}
int main() 
{
	int n;scanf("%d",&n);
	memset(s,0,sizeof(s));
	for(int i=1,tot=0; i<=n; i++) 
	{
		char c;scanf(" %c",&c);
		if(c=='A') 
		{
			int L,R,cnt=0;
			scanf("%d%d",&L,&R);
			while(1) 
			{
				int l=1,r=R,p;//二分找重叠区的起点
				while(l<=r)
				{
					int mid=(l+r)>>1;
					if(sum(mid)==sum(R))r=mid-1,p=mid;
					else  l=mid+1; 
				}

				if(ed[p]>=L) //有重叠则删除
				{  
					change(p,-1); //区间[p,N]-1
					ed[p]=0;
					cnt++;        //重叠区间数+1
					tot--;        //总区间数-1
				} else break;     //无重叠则退出
			}
			printf("%d\n",cnt);
			change(L,1); //区间[L,N]+1
			ed[L]=R;     //存区间[L,R]
			tot++;       //总区间数+1
		}
		else printf("%d\n",tot);
	}
	return 0;
}