[P4064][JXOI2017]加法(贪心+树状数组+堆)

不要相信数据范围，应该是$1\leq n,m \leq 10^5$。

二分答案，贪心扫一遍，对于小于二分值的位置，用堆找到包含它且向右延伸最长的区间加上它，区间加用差分树状数组实现。

 #include<cstdio>

 #include<queue>

 #include<cstring>

 #include<algorithm>

 #define rep(i,l,r) for (int i=l; i<=r; i++)

 using namespace std;

 const int N=;

 priority_queue<int>Q;

 int T,n,m,k,A,q[N],a[N],c[N],stk[N];

 struct P{ int l,r; }p[N];

 bool cmp(P a,P b){ return a.l<b.l; }

 void add(int x,int k){ for (; x<=n+; x+=x&-x) c[x]+=k; }

 int que(int x){ int res=; for (; x; x-=x&-x) res+=c[x]; return res; }

 bool chk(int lim){

     while (!Q.empty()) Q.pop();

     memset(c,,sizeof(c)); int top=,j=,cnt=;

     rep(i,,n) if (a[i]<lim) stk[++top]=i;

     rep(i,,top){

         while (j<=m && p[j].l<=stk[i]) Q.push(p[j].r),j++;

         while (a[stk[i]]+que(stk[i])<lim){

             cnt++; if (cnt>k || Q.empty()) return ;

             int x=Q.top(); Q.pop(); add(stk[i],A); add(x+,-A);

         }

     }

     return ;

 }

 int main(){

     freopen("P4064.in","r",stdin);

     freopen("P4064.out","w",stdout);

     for (scanf("%d",&T); T--; ){

         scanf("%d%d%d%d",&n,&m,&k,&A);

         rep(i,,n) scanf("%d",&a[i]);

         rep(i,,m) scanf("%d%d",&p[i].l,&p[i].r);

         sort(p+,p+m+,cmp);

         int l=,r=,mid,ans;

         while (l<=r){

             mid=(l+r)>>;

             if (chk(mid)) ans=mid,l=mid+; else r=mid-;

         }

         printf("%d\n",ans);

     }

     return ;

 }