不要相信数据范围，应该是$1\leq n,m \leq 10^5$。
二分答案，贪心扫一遍，对于小于二分值的位置，用堆找到包含它且向右延伸最长的区间加上它，区间加用差分树状数组实现。
1 #include<cstdio> 2 #include<queue> 3 #include<cstring> 4 #include<algorithm> 5 #define rep(i,l,r) for (int i=l; i<=r; i++) 6 using namespace std; 7 8 const int N=200100; 9 priority_queue<int>Q; 10 int T,n,m,k,A,q[N],a[N],c[N],stk[N]; 11 struct P{ int l,r; }p[N]; 12 bool cmp(P a,P b){ return a.l<b.l; } 13 void add(int x,int k){ for (; x<=n+1; x+=x&-x) c[x]+=k; } 14 int que(int x){ int res=0; for (; x; x-=x&-x) res+=c[x]; return res; } 15 16 bool chk(int lim){ 17 while (!Q.empty()) Q.pop(); 18 memset(c,0,sizeof(c)); int top=0,j=1,cnt=0; 19 rep(i,1,n) if (a[i]<lim) stk[++top]=i; 20 rep(i,1,top){ 21 while (j<=m && p[j].l<=stk[i]) Q.push(p[j].r),j++; 22 while (a[stk[i]]+que(stk[i])<lim){ 23 cnt++; if (cnt>k || Q.empty()) return 0; 24 int x=Q.top(); Q.pop(); add(stk[i],A); add(x+1,-A); 25 } 26 } 27 return 1; 28 } 29 30 int main(){ 31 freopen("P40.in","r",stdin); 32 freopen("P40.out","w",stdout); 33 for (scanf("%d",&T); T--; ){ 34 scanf("%d%d%d%d",&n,&m,&k,&A); 35 rep(i,1,n) scanf("%d",&a[i]); 36 rep(i,1,m) scanf("%d%d",&p[i].l,&p[i].r); 37 sort(p+1,p+m+1,cmp); 38 int l=1,r=120000000,mid,ans; 39 while (l<=r){ 40 mid=(l+r)>>1; 41 if (chk(mid)) ans=mid,l=mid+1; else r=mid-1; 42 } 43 printf("%d\n",ans); 44 } 45 return 0; 46 }