4.Fast Arrangement

4.Fast Arrangement

Chinese always have the railway tickets problem because of its' huge amount of passangers and
stations. Now goverment need you to develop a new tickets query system. One train can just take
k passangers. And each passanger can just buy one ticket from station a to station b. Each train
cannot take more passangers any time. The one who buy the ticket earlier which can be sold will
always get the ticket.

输入

The input contains servel test cases. The first line is the case number. In each test case:
The first line contains just one number k( 1 ≤ k ≤ 1000 ) and Q( 1 ≤ Q ≤ 100000 )
The following lines, each line contains two integers a and b, ( 1 ≤ a < b ≤ 1000000 ),
indicate a query.
Huge Input, scanf recommanded.

输出

For each test case, output three lines:
Output the case number in the first line.
If the ith query can be satisfied, output i. i starting from 1. output an blank-space after
each number.
Output a blank line after each test case.

样例输入

1
3 6
1 6
1 6
3 4
1 5
1 2
2 4

样例输出

Case 1:
1 2 3 5 

ac代码

#include<cstdio>
#include<cstring>
#include<vector>

using namespace std;
const int maxl=1e6+5;
int n,q,cont;
struct node {int l,r,max_;
int tag;};

node tree[maxl<<2];
vector<int> ans;


int max(int a,int b){
    return a>b?a:b;
}
void build(int k,int l,int r)
{
    tree[k].l=l;tree[k].r=r;
    if(l==r)
    {   
        tree[k].max_=0;
        return;
    }
    int mid=(tree[k].l+tree[k].r)>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
    tree[k].max_=max(tree[k<<1].max_,tree[k<<1|1].max_);
}


void change(int k)
{
    if(tree[k].l==tree[k].r){
        tree[k].tag=0;
        
        return;
    }
    //  tree[k].max_+=tree[k].tag;
        tree[k<<1].tag+=tree[k].tag;
        tree[k<<1|1].tag+=tree[k].tag;
        tree[k<<1].max_+=tree[k].tag;
        tree[k<<1|1].max_+=tree[k].tag;
        tree[k].tag=0;
}

void add(int k,int l,int r,int x)
{
    if(tree[k].tag)
        change(k);
    if(tree[k].l==l && tree[k].r==r)
    {
        tree[k].max_+=x;
        tree[k].tag+=x;
        return;
    }
    int mid=(tree[k].l+tree[k].r)>>1;
    if(r<=mid)
        add(k<<1,l,r,x);
    else
        if(l>mid)
            add(k<<1|1,l,r,x);
        else
            add(k<<1,l,mid,x),add(k<<1|1,mid+1,r,x);
    tree[k].max_=max(tree[k<<1].max_,tree[k<<1|1].max_);
}

int query(int k,int l,int r)
{
    if(tree[k].tag)
        change(k);
    int max_,mid=(tree[k].l+tree[k].r)>>1;
    if(tree[k].l==l && tree[k].r==r)
        return tree[k].max_;
    if(r<=mid)
        return query(k<<1,l,r);
    else
        if(l>mid)
            return query(k<<1|1,l,r);
        else
            return max(query(k<<1,l,mid),query(k<<1|1,mid+1,r));
}
void prework()
{
    scanf("%d",&n);
    //for(int i=1;i<=n;i++)
    //  scanf("%lld",&a[i]);
    scanf("%d",&q);
    //memset(a,0,sizeof(a));
    memset(tree,0,sizeof(tree));
    build(1,1,maxl-5);
}

void mainwork()
{
    int l,r,d,x;
    for(int i=1;i<=q;i++)
    {
        
        scanf("%d%d",&l,&r);
        add(1,l,r-1,1);
        //printf("treemax:%lld\n",query(1,1,maxl));
        if(tree[1].max_>n){
            add(1,l,r-1,-1);
        }
        else
        {

            //printf("%lld ",i);
            ans.push_back(i);
        }       
    }
    printf("Case %d:\n",cont);
    for(auto i : ans){
        printf("%d ",i);
    }
    printf("\n\n");
}

int main()
{
    int t;
    scanf("%d",&t);
    
    for(cont = 1;cont<=t;cont++){
        ans.clear();
        prework();
        mainwork();
        
    }
    return 0;
}