评测记录

#include <iostream>
#include <vector>
using namespace std;
const int p=3e7,q=1e6;
template <class type>
class segment_tree
{
    private:
        template <class node_type>
        struct node
        {
            int l,r;
            int ls,rs;
            node_type sum;
        };
        node<type> t[p+5];
        int cur,root[q+5];
        inline int mid(int l,int r)
        {
            return (l+r)/2;
        }
        inline void create(int id)
        {
            if(t[id].l!=t[id].r&&t[id].ls==0)
            {
                cur++;
                t[id].ls=cur;
                t[t[id].ls].l=t[id].l;
                t[t[id].ls].r=mid(t[id].l,t[id].r);
                cur++;
                t[id].rs=cur;
                t[t[id].rs].l=mid(t[id].l,t[id].r)+1;
                t[t[id].rs].r=t[id].r;
            }
        }
        void change_(int hid,int id,int x,type delta)
        {
            t[id].sum+=delta;
            if(t[id].l==t[id].r&&t[id].l==x)
                return ;
            create(hid);
            if(x<=mid(t[id].l,t[id].r))
            {
                t[id].rs=t[hid].rs;
                cur++;
                t[id].ls=cur;
                t[cur].l=t[id].l;
                t[cur].r=mid(t[id].l,t[id].r);
                t[cur].sum=t[t[hid].ls].sum;
                change_(t[hid].ls,t[id].ls,x,delta);
            }
            else
            {
                t[id].ls=t[hid].ls;
                cur++;
                t[id].rs=cur;
                t[cur].l=mid(t[id].l,t[id].r)+1;
                t[cur].r=t[id].r;
                t[cur].sum=t[t[hid].rs].sum;
                change_(t[hid].rs,t[id].rs,x,delta);
            }
        }
        type request_(int id,int l,int r)
        {
            if(t[id].l==l&&t[id].r==r)
                return t[id].sum;
            create(id);
            int mid_=mid(t[id].l,t[id].r);
            bool f1=l<=mid_,f2=mid_+1<=r;
            if(f1&&!f2)
                return request_(t[id].ls,l,r);
            else if(!f1&&f2)
                return request_(t[id].rs,l,r);
            else if(f1&&f2)
                return request_(t[id].ls,l,mid_)+request_(t[id].rs,mid_+1,r);
        }
    public:
        void build(int minium,int maxium)
        {
            cur++;
            root[0]=cur;
            t[cur].l=minium;
            t[cur].r=maxium;
        }
        void change(int hid,int id,int x,type delta)
        {
            cur++;
            t[cur].l=t[root[0]].l;
            t[cur].r=t[root[0]].r;
            t[cur].sum=t[root[hid]].sum;
            root[id]=cur;
            change_(root[hid],root[id],x,delta);
        }
        type request(int id,int l,int r)
        {
            return request_(root[id],l,r);
        }
};
segment_tree<int> t;
int n,m,a[200005],l[200005],r[200005],s[200005];
int ans[200005];
int f(int l_,int r_,int id)//确定第id号木板是在什么时候被击碎的 
{
	if(l_==r_)
		return l_;
	int mid=(l_+r_)/2;
	if(t.request(mid,l[id],r[id])>=s[id])
		return f(l_,mid,id);
	return f(mid+1,r_,id);
}
int main()
{
//	freopen("data.in","r",stdin);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0); 
	t.build(1,(int)(2e5));
	cin>>n>>m;
	for(int i=1;i+7<=n;i+=8)
	{
		cin>>l[i+0]>>r[i+0]>>s[i+0];
		cin>>l[i+1]>>r[i+1]>>s[i+1];
		cin>>l[i+2]>>r[i+2]>>s[i+2];
		cin>>l[i+3]>>r[i+3]>>s[i+3];
		cin>>l[i+4]>>r[i+4]>>s[i+4];
		cin>>l[i+5]>>r[i+5]>>s[i+5];
		cin>>l[i+6]>>r[i+6]>>s[i+6];
		cin>>l[i+7]>>r[i+7]>>s[i+7];
	}
	switch(n%8)
	{
		case 7:
			cin>>l[n-6]>>r[n-6]>>s[n-6];
		case 6:
			cin>>l[n-5]>>r[n-5]>>s[n-5];
		case 5:
			cin>>l[n-4]>>r[n-4]>>s[n-4];
		case 4:
			cin>>l[n-3]>>r[n-3]>>s[n-3];
		case 3:
			cin>>l[n-2]>>r[n-2]>>s[n-2];
		case 2:
			cin>>l[n-1]>>r[n-1]>>s[n-1];
		case 1:
			cin>>l[n-0]>>r[n-0]>>s[n-0];
	}
	for(int i=1;i+7<=m;i+=8)
	{
		cin>>a[i+0];t.change(i-1,i+0,a[i+0],1);
		cin>>a[i+1];t.change(i+0,i+1,a[i+1],1);
		cin>>a[i+2];t.change(i+1,i+2,a[i+2],1);
		cin>>a[i+3];t.change(i+2,i+3,a[i+3],1);
		cin>>a[i+4];t.change(i+3,i+4,a[i+4],1);
		cin>>a[i+5];t.change(i+4,i+5,a[i+5],1);
		cin>>a[i+6];t.change(i+5,i+6,a[i+6],1);
		cin>>a[i+7];t.change(i+6,i+7,a[i+7],1);
	}
	switch(m%8)
	{
		case 7:
			cin>>a[m-6];t.change(m-7,m-6,a[m-6],1);
		case 6:
			cin>>a[m-5];t.change(m-6,m-5,a[m-5],1);
		case 5:
			cin>>a[m-4];t.change(m-5,m-4,a[m-4],1);
		case 4:
			cin>>a[m-3];t.change(m-4,m-3,a[m-3],1);
		case 3:
			cin>>a[m-2];t.change(m-3,m-2,a[m-2],1);
		case 2:
			cin>>a[m-1];t.change(m-2,m-1,a[m-1],1);
		case 1:
			cin>>a[m-0];t.change(m-1,m-0,a[m-0],1);
	}
	t.change(0,m+1,1,0);
	for(int i=1;i<=n;i++)
		ans[f(0,m+1,i)]++;
	for(int i=1;i+7<=m;i+=8)
	{
		cout<<ans[i+0]<<"\n";
		cout<<ans[i+1]<<"\n";
		cout<<ans[i+2]<<"\n";
		cout<<ans[i+3]<<"\n";
		cout<<ans[i+4]<<"\n";
		cout<<ans[i+5]<<"\n";
		cout<<ans[i+6]<<"\n";
		cout<<ans[i+7]<<"\n";
	}
	switch(m%8)
	{
		case 7:
			cout<<ans[m-6]<<"\n";
		case 6:
			cout<<ans[m-5]<<"\n";
		case 5:
			cout<<ans[m-4]<<"\n";
		case 4:
			cout<<ans[m-3]<<"\n";
		case 3:
			cout<<ans[m-2]<<"\n";
		case 2:
			cout<<ans[m-1]<<"\n";
		case 1:
			cout<<ans[m-0]<<"\n";
	}
	return 0;
}