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.

Input
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.

Output
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.

Sample Input
1
3 6
1 6
1 6
3 4
1 5
1 2
2 4

Sample Output
Case 1:
1 2 3 5

题意：
火车买票，火车最多能搭载K人，有Q个人去买票，输出谁能买到票

易错点：
1.数据规模多0少0
一开始以为Q和a,b的数据规模是一样的，maxn少了个0，然后就<mark>Runtime Error(ACCESS_VIOLATION)</mark>
英语不好，读题就炸了
2.本题的lazy是给它的孩子区间+1，而不是加上区间长度*lazy
3.某区间车上有多少人是它左右孩子的最大值而不是和
4.乘车区间前闭后开

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1000005;
struct node{
	int l,r,sum,lazy;
}tr[maxn<<2];
int q[maxn];
void pushup(int m){
	tr[m].sum=max(tr[m<<1].sum,tr[m<<1|1].sum);
}
void build(int m,int l,int r){
	tr[m].l=l;
	tr[m].r=r;
	tr[m].lazy=0;
	if(l==r){
		tr[m].sum=0;
		return ;
	}
	int mid=(l+r)>>1;
	build(m<<1,l,mid);
	build(m<<1|1,mid+1,r);
	pushup(m);
}
void pushdown(int m){
	if(tr[m].lazy){
		tr[m<<1].lazy+=tr[m].lazy;
		tr[m<<1|1].lazy+=tr[m].lazy;
		tr[m<<1].sum+=tr[m].lazy;
		tr[m<<1|1].sum+=tr[m].lazy;
		tr[m].lazy=0;
	}
}
void updata(int m,int l,int r,int val){
	if(tr[m].l==l&&tr[m].r==r){
		tr[m].sum+=val;
		tr[m].lazy+=val;
		return ;
	}
	pushdown(m);
	int mid=(tr[m].l+tr[m].r)>>1;
	if(r<=mid) updata(m<<1,l,r,val);
	else if(l>mid) updata(m<<1|1,l,r,val);
	else {
		updata(m<<1,l,mid,val);
		updata(m<<1|1,mid+1,r,val);
	}
	pushup(m);
}
int query(int m,int l,int r){
	if(tr[m].l==l&&tr[m].r==r){
		return tr[m].sum;
	}
	pushdown(m);
	int mid=(tr[m].l+tr[m].r)>>1;
	int temp;
	if(r<=mid) temp=query(m<<1,l,r);
	else if(l>mid) temp=query(m<<1|1,l,r);
	else temp=max(query(m<<1,l,mid),query(m<<1|1,mid+1,r));
	return temp;
}
int main(){
	int T,K,Q,a,b,t=1;
	scanf("%d",&T);
	for(int t=1;t<=T;t++){
		int top=0;
		scanf("%d%d",&K,&Q);
		build(1,1,1000000);
		for(int i=1;i<=Q;i++){
			scanf("%d%d",&a,&b);
			b--;//前闭后开 
			if(query(1,a,b)<K){
				q[top++]=i;
				updata(1,a,b,1);
			}
		}
		printf("Case %d:\n",t);
		for(int i=0;i<top;i++)
		printf("%d ",q[i]);
		printf("\n\n");
	}
	return 0;
}