rt

分块艹到最优解第一页

record

#include<bits/stdc++.h>
#define max(x,y) (x)>(y)?(x):(y)
#define min(x,y) (x)<(y)?(x):(y)
using namespace std;
char buf[1<<21], *p1 = buf, *p2 = buf;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline void read(int &x) {
	x = 0;
	bool f = 0;
	char c = gc();
	while (c < '0' || c > '9') {
		c == '-' ? f = 1 : 0;
		c = gc();
	}
	while (c >= '0' && c <= '9') {
		x = (x<<3)+(x<<1)+(c^48), c = gc();
	}
	f ? x = -x : 0;
}
inline void write(register int &x) {
	static int sta[35];
	register int top = 0;
	do {
		sta[top++] = x % 10, x /= 10;
	} while (x);
	while (top) putchar_unlocked(sta[--top] + 48);
}
struct kuai {
	int mx;
	int l;
	int r;
	int mn;
};
int X;
int meikuai,meikuku;
kuai block[50005];
struct kuku {
	int kukumx;
	int kul;
	int kur;
	int kukumn;
};
kuku tao[20005];
int c[100005];
inline int getkuai(register int &x) {
	return (x-1)/meikuai+1;
}
inline int getkuku(register int &x) {
	return (x-1)/meikuku+1;
}
int main() {
	register int a,b;
	read(a),read(b);
	for(register int i=1; i<=a; ++i) {
		read(c[i]);
	}
	meikuai=(int)pow(a,1.0/3);
	register int mn=INT_MAX,mx=INT_MIN,cnt=1;
	for(register int i=1; i<=a; ++i) {
		mn=min(c[i],mn);
		mx=max(c[i],mx);
		if(i%meikuai==0) {
			block[cnt].mn=mn;
			block[cnt].mx=mx;
			block[cnt].l=block[cnt-1].r+1;
			block[cnt].r=i;
			mn=INT_MAX;
			mx=INT_MIN;
			cnt++;
		}
	}
	if((int)pow(a,1.0/3)*(int)pow(a,1.0/3)*(int)pow(a,1.0/3)!=a) {
		block[cnt].mn=mn;
		block[cnt].mx=mx;
		block[cnt].l=block[cnt-1].r+1;
		block[cnt].r=a;
		cnt++;
	}
	mn=INT_MAX;
	mx=INT_MIN;
	meikuku=(int)pow(cnt,1.0/3);
	int kukucnt=1;
	for(register int i=1; i<=cnt; ++i) {
		mn=min(block[i].mn,mn);
		mx=max(block[i].mx,mx);
		if(i%meikuku==0) {
			tao[kukucnt].kukumn=mn;
			tao[kukucnt].kukumx=mx;
			tao[kukucnt].kul=tao[kukucnt-1].kur+1;
			tao[kukucnt].kur=i;
			mn=INT_MAX;
			mx=INT_MIN;
			kukucnt++;
		}
	}
	if((int)pow(cnt,1.0/3)*(int)pow(cnt,1.0/3)*(int)pow(cnt,1.0/3)!=cnt) {
		tao[kukucnt].kukumn=mn;
		tao[kukucnt].kukumx=mx;
		tao[kukucnt].kul=tao[kukucnt-1].kur+1;
		tao[kukucnt].kur=cnt;
		kukucnt++;
	}
	register int quel,quer,lid,rid,kul,kur;//块的长度n的立方根时时间最优（应该）
	for(register int i=0; i<b; ++i) {
		read(quel);
		read(quer);
		lid=getkuai(quel);
		rid=getkuai(quer);
		kul=getkuku(lid);
		kur=getkuku(rid);
		mn=INT_MAX;
		mx=INT_MIN;
		if(lid==rid) {
			for(register int n=quel; n<=quer; ++n) {
				mn=min(c[n],mn);
				mx=max(c[n],mx);
			}
		} else {
			for(register int n=quel; n<=block[lid].r; ++n) {
				mn=min(mn,c[n]);
				mx=max(c[n],mx);
			}
			if(kul==kur) {
				for(register int n=lid+1; n<rid; ++n) {
					mn=min(block[n].mn,mn);
					mx=max(block[n].mx,mx);
				}
			} else {
				for(register int n=lid+1; n<=tao[kul].kur; ++n) {
					mn=min(block[n].mn,mn);
					mx=max(block[n].mx,mx);
				}
				for(register int n=kul+1; n<kur; ++n) {
					mn=min(tao[n].kukumn,mn);
					mx=max(tao[n].kukumx,mx);
				}
				for(register int n=tao[kur].kul; n<rid; ++n) {
					mn=min(block[n].mn,mn);
					mx=max(block[n].mx,mx);
				}
			}
			for(register int n=block[rid].l; n<=quer; ++n) {
				mn=min(mn,c[n]);
				mx=max(c[n],mx);
			}
		}
		write(X = mx-mn);
		putchar_unlocked('\n');
	}
	return 0;
}