传送门
毒瘤lxl数据结构题。
首先,考虑传统的ST表,发现n=2000000,空间开不下。
考虑分块+ST表,每个块里面存的是块内前缀最大值,后缀最大值。
最后ST表查询的是块的最大值。
注意查询的区间[l,r]在同一块内需要暴力搞一下,发现数据随机,所以出现这种情况不多。
为了卡常数,需要预处理log,注意查询时要特判l>r
还有一点非常玄学,块大小要开5000,要不然会TLE
时间复杂度O(n+log5000×5000+a×5000+b),其中a表示查询区间[l,r]在同一块的情况总数,b表示查询区间[l,r]不在同一块的情况总数。
空间复杂度O(n+log5000×5000),反正不会MLE
注意此代码常数蜃大,提交前需要洗一把脸。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101
| #include <bits/stdc++.h> #define MAXN 20000005 #define BMAX 5005 #define STMAX 13 #define max(a,b) (a>b?a:b) #define min(a,b) (a<b?a:b) using namespace std; inline int read(){ int x=0,f=1; char ch=getchar(); while (ch<'0'||ch>'9'){ if (ch=='-') f=-1; ch=getchar(); } while (ch>='0'&&ch<='9'){ x=(x<<3)+(x<<1)+(ch^'0'); ch=getchar(); } return x*f; } namespace GenHelper{ unsigned z1,z2,z3,z4,b; inline 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); } } inline void srand(unsigned x){ using namespace GenHelper; z1=x; z2=(~x)^0x233333333U; z3=x^0x1234598766U; z4=(~x)+51; } inline int _read(){ using namespace GenHelper; return (rand_()&32767)*32768+(rand_()&32767); } static int Block_L[MAXN],Block_R[MAXN],a[MAXN]; static int id[MAXN],lg[BMAX]; int Size;
static int ST[STMAX][BMAX]; inline void Init_ST(int n){ for (register int i=1;i<STMAX;++i){ for (register int j=1;j+(1<<i)-1<BMAX;++j){ ST[i][j]=max(ST[i-1][j],ST[i-1][j+(1<<(i-1))]); } } } inline int Query(int l,int r){ if (l>r) return 0; int k=lg[r-l+1]; return max(ST[k][l],ST[k][r-(1<<k)+1]); } inline void Init(int n){ for (register int i=1;i<=n;++i){ Block_L[i]=(((id[i]-1)*Size+1)==i)?a[i]:max(Block_L[i-1],a[i]); } for (register int i=n;i>=1;--i){ Block_R[i]=(min(id[i]*Size,n)==i)?a[i]:max(Block_R[i+1],a[i]); } for (register int i=1;i<=n;++i){ ST[0][id[i]]=max(ST[0][id[i]],a[i]); } Init_ST(n); } #define ull unsigned long long int main(){ int n=read(),m=read(),s=read(); srand(s); Size=5000; for (register int i=1;i<=n;++i){ a[i]=_read(); id[i]=(i-1)/Size+1; } lg[0]=-1; for (register int i=1;i<BMAX;++i) lg[i]=lg[i>>1]+1; Init(n); ull ans=0; while (m--){ int l=_read()%n+1,r=_read()%n+1; if (l>r) swap(l,r); if (id[l]==id[r]){ int maxn=0; for (register int i=l;i<=r;++i){ maxn=max(maxn,a[i]); } ans+=(ull)maxn; } else { ans+=(ull)(max(max(Block_L[r],Block_R[l]),Query(id[l]+1,id[r]-1))); } } cout<<ans<<endl; }
|