RT

TLE #2 #10

实在卡不动了/kk

#pragma GCC diagnostic error "-std=c++11"
#pragma GCC target("avx")
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define N 10000
namespace GenHelper{
	unsigned z1,z2,z3,z4,b;
	unsigned rand_(){
		b=((z1<<6)^z1)>>13;
		z1=((z1&4294967294U)<<18)^b;
		b=((z2<<2)^z2)>>27;
		z2=((z2&4294967288U)<<2)^b;
		b=((z3<<13)^z3)>>21;
		z3=((z3&4294967280U)<<7)^b;
		b=((z4<<3)^z4)>>12;
		z4=((z4&4294967168U)<<13)^b;
		return (z1^z2^z3^z4);
	}
}
void srand(unsigned x){
	using namespace GenHelper;
	z1=x,z2=(~x)^0x233333333U,z3=x^0x1234598766U,z4=(~x)+51;
}
int read(){
	using namespace GenHelper;
	int a=rand_()&32767;
	int b=rand_()&32767;
	return a*32768+b;
}
int maxl[20000005],maxr[20000005];
int a[20000005],b[20000005],f[15][N],lg[N],p[15]={1},blo,n,m,s;
void init(){
	for(register int i=1;i<=n;i++)
		b[i]=(i-1)/blo+1;
	int x;
	for(register int i=1;blo*(i-1)+1<=n;i++){
		int tmp=(i-1)*blo;
		x=min(blo,n-tmp);
		maxl[tmp+1]=a[tmp+1],maxr[tmp+x]=a[tmp+x];
		for(register int j=2;j<=x;j++)
			maxl[tmp+j]=max(maxl[tmp+j-1],a[tmp+j]);
		for(register int j=x-1;j>0;j--)
			maxr[tmp+j]=max(maxr[tmp+j+1],a[tmp+j]);
		f[0][i]=maxl[tmp+x];
	}
	for(register int i=1;i<15;i++)
		p[i]=p[i-1]<<1;
	lg[0]=-1;
	for(register int i=1;i<N;i++)
		lg[i]=lg[i>>1]+1;
	for(register int j=1;j<15;j++)
		for(register int i=1;i+p[j]<=n/blo+3;i++)
			f[j][i]=max(f[j-1][i],f[j-1][i+p[j-1]]);
}
signed main(){
//	freopen("P3793.in","r",stdin);
//	freopen("out.out","w",stdout);
	scanf("%d%d%d",&n,&m,&s);
	srand(s);
	blo=sqrt(n)/2+1;
	for(register int i=1;i<=n;i++)
		a[i]=read();
	init();
	int l,r,kkak;
	long long ans=0;
	while(m--){
//		if(m%1000000==0)cout<<m<<endl;
		l=read()%n+1,r=read()%n+1;
		if(l>r)l^=r^=l^=r;
		if(b[l]+1==b[r])ans+=max(maxr[l],maxl[r]);
		else if(b[l]==b[r]){
			kkak=0;
			for(register int i=l;i<=r;i++)
				kkak=kkak<a[i]?a[i]:kkak;
			ans+=kkak;
		}
		else kkak=lg[b[r]-b[l]-1],ans+=max(max(f[kkak][b[l]+1],f[kkak][b[r]-p[kkak]]),max(maxr[l],maxl[r]));
	}
	printf("%lld",ans);
	return 0;
}