1. 使用快读；
2. 这道题让你用分治，你就好好用分治做~~（考试考了怎么办……）~~

//示例
void read(int &x){ 

	int f=1;x=0;char s=getchar();

	while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}

	while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}

	x*=f;

}