曲靖网站建设公司靖网站建设,北京网站设计联系电话,wordpress文章页打不开了,深圳手机网站P4064 [JXOI2017]加法
题意#xff1a;
题解#xff1a;
要求找最小值尽可能大#xff0c;很明显二分#xff0c;现在是如何判断二分出来的答案的正确性 对于一个二分出来的答案mid#xff0c;要求对k个区间进行操作后#xff0c;最小值大于mid#xff0c;我们可以这…P4064 [JXOI2017]加法
题意
题解
要求找最小值尽可能大很明显二分现在是如何判断二分出来的答案的正确性 对于一个二分出来的答案mid要求对k个区间进行操作后最小值大于mid我们可以这样实现对于第i位(前i-1位已经处理完毕且前i-1位均大于等于mid)此时我们要找的区间是要包含第i位的也就是区间的左端点一定小于等于i而对于右端点一定是越远越好右端点越远就可以让更多的数增加更容易使得所有数都大于等于mid 怎么才能实现合理选取区间这个操作我们用一个最大堆每次将左端点小于i的区间加入其中然后选取堆顶的区间。因为我们是从左往右依次处理那么这个堆就可以继承给下一个点使用
代码
#include bits/stdc.h
#include unordered_map
#define debug(a, b) printf(%s %d\n, a, b);
using namespace std;
bool Handsome;
typedef long long ll;
typedef unsigned long long ull;
typedef pairint, int PII;
clock_t startTime, endTime;
//Fe~Jozky
const ll INF_ll 1e18;
const int INF_int 0x3f3f3f3f;
void read(){};
template typename _Tp, typename... _Tps void read(_Tp x, _Tps... Ar)
{x 0;char c getchar();bool flag 0;while (c 0 || c 9)flag| (c -), c getchar();while (c 0 c 9)x (x 3) (x 1) (c ^ 48), c getchar();if (flag)x -x;read(Ar...);
}
template typename T inline void write(T x)
{if (x 0) {x ~(x - 1);putchar(-);}if (x 9)write(x / 10);putchar(x % 10 0);
}
void rd_test(bool Most)
{
#ifdef ONLINE_JUDGE
#elseprintf(%.2lfMB\n,(Most-Handsome)/1024.0/1024.0);startTime clock ();freopen(data.in, r, stdin);
#endif
}
void Time_test()
{
#ifdef ONLINE_JUDGE
#elseendTime clock();printf(\nRun Time:%lfs\n, (double)(endTime - startTime) / CLOCKS_PER_SEC);
#endif
}
const int maxn3e59;
#define int long long
int A[maxn];
int n,m,k,a;
int lowbit(int x){return x(-x);
}
struct node{int l,r;bool operator(const node x)const{return rx.r;}
};
int V[maxn];
struct nod{int l,r;
};
nod q[maxn];
nod x;
int N2e59;
void add(int x,int val){for(int ix;iN;ilowbit(i)){V[i]val;}
}
ll query(int x){ll sum0;for(int ix;i;i-lowbit(i)){sumV[i];} return sum;
}
bool check(int mid){memset(V,0,sizeof(V));priority_queuenodeQ;for(int i1;in;i){add(i,A[i]-A[i-1]);}int tot0;int num1;for(int i1;in;i){while(q[num].linumm){Q.push((node){q[num].l,q[num].r});num;}while(query(i)midQ.size()){node xQ.top();Q.pop();if(x.ri||totk)return 0;add(x.l,a);add(x.r1,-a);}if(query(i)mid)return 0;}return 1;
}
int val[maxn];
bool Most;
bool cmp(nod x,nod y){return x.ly.l;
}
signed main()
{
// rd_test(Most);int t;read(t);while(t--){int minn1e189;int maxx0;read(n,m,k,a);for(int i1;in;i){read(A[i]);minnmin(A[i],minn);maxxmax(A[i],maxx);}for(int i1;im;i){read(q[i].l,q[i].r);}sort(q1,q1m,cmp);int ans;int lminn,rmaxxk*a;while(lr){int midlr1;if(check(mid)){ansmid;lmid1;}else rmid-1;}printf(%lld\n,ans);}//Time_test();
}
