微信网站制作免费,百度为什么打不开网页无法访问,Mui框架做网站,html5网页设计论文我手把手教她打扑克 qwq
综合分析一下2个操作#xff0c;查找区间第k小的值#xff0c;感觉可以用主席树#xff0c;区间修改那没事了
考虑分块做法,块长B
分析第一个操作
只需要维护数列的单调性#xff0c;然后二分答案上二分就ok了
分析第二个操作
维护一个加法懒…我手把手教她打扑克 qwq
综合分析一下2个操作查找区间第k小的值感觉可以用主席树区间修改那没事了
考虑分块做法,块长B
分析第一个操作
只需要维护数列的单调性然后二分答案上二分就ok了
分析第二个操作
维护一个加法懒标记即可
口胡了一下感觉很简单
仔细分析一下第一个操作
二分找到一个“第k小值”再进行check,check的过程中散块遍历一遍整块二分找到最后一个小于等于x的只有前面部分有贡献分析一下时间复杂度,预处理 ,(分块完排序)二分答案,二分
第二个操作
散块可以暴力然后重构整块上懒标记时间复杂度
总时间复杂度 maybe..
应该需要优化
分析一下二分答案这块我们不一定要把L定义无穷小R定义无穷大可以维护一下区间最大值区间最小值这样可以转化为差不多能卡过去了我是这样干的二分剪枝一下
分析一下散块区间加不一定要的排序我们可以把数列分成2块没有加的和加的两边其实都是有序的因此可以用归并排序优化成
快长最优可能是..
小优化
1.不一定要把散块重构如果没有询问到可以不做我们用线段树区间赋值的思想修改后标记一下这个块需要重构等询问的时候问到了再进行重构
void work(int l,int r){int ppos[l];int qpos[r];for(int ip;iq;i){if(re[i]){rebuild(i);re[i]0;}}
}
2.二分答案优化 if(k1 || R-L1k){return -1;}
3.块内二分优化 if(v[id].front()add[id]x){//没有比x小的return 0;}if(v[id].back()add[id]x){//都是小于等于x的return r1;//r-01;}
4.维护区间最大值最小值优化 for(int ip1;iq-1;i){//最后一个是最大resmax(res,v[i].back()add[i]);}for(int ip1;iq-1;i){//第一个是最小resmin(res,v[i].front()add[i]);}
完整代码
#includeiostream
#includecmath
#includealgorithm
#includebitset
#includecstring
#includevector
#define INF (1ll60)
using namespace std;
typedef long long ll;
const int N1e59;
const int B1e49;
namespace Lan {inline string sread() {string s ;char egetchar();while(e ||e\n)egetchar();while(e! e!\n)se,egetchar();return s;}inline void swrite(string s){for(char e:s)putchar(e);printf(\n);}inline ll read() {ll x0,y1;char cgetchar();while(!isdigit(c)){if(c-)y-1;cgetchar();}while(isdigit(c)){x(x3)(x1)(c^48);cgetchar();}return x*y;}inline void write(ll x) {if(x0){x-x,putchar(-);}ll sta[35],top0;do sta[top]x%10,x/10;while(x);while(top)putchar(sta[--top]0);}
}using namespace Lan;
ll a[N];
int L[B],R[B],pos[N];
ll add[B];
int re[B];
vectorll v[B];
inline void rebuild(int id){v[id].clear();for(int iL[id];iR[id];i){v[id].push_back(a[i]);}sort(v[id].begin(),v[id].end());
}
inline int binary(int id,int x){int l0,rv[id].size()-1;if(v[id].front()add[id]x){//没有比x小的return 0;}if(v[id].back()add[id]x){//都是小于等于x的return r1;//r-01;}int res0;while(lr){int mid(lr)1;if(v[id][mid]add[id]x){//小于等于x选大一点lmid1;resmid1;//小于等于x的有贡献}else{rmid-1;}}return res;
}
inline ll getmax(int l,int r){ll res-INF;int ppos[l];int qpos[r];if(pq){for(int il;ir;i){resmax(res,a[i]add[pos[i]]);}}else{for(int il;iR[p];i){resmax(res,a[i]add[pos[i]]);}for(int iL[q];ir;i){resmax(res,a[i]add[pos[i]]);}for(int ip1;iq-1;i){//最后一个是最大resmax(res,v[i].back()add[i]);}} return res;
}
inline ll getmin(int l,int r){ll resINF;int ppos[l];int qpos[r];if(pq){for(int il;ir;i){resmin(res,a[i]add[pos[i]]);}}else{for(int il;iR[p];i){resmin(res,a[i]add[pos[i]]);}for(int iL[q];ir;i){resmin(res,a[i]add[pos[i]]);}for(int ip1;iq-1;i){//第一个是最小resmin(res,v[i].front()add[i]);}}return res;
}
inline int check(int l,int r,int x){int ppos[l];int qpos[r];int res0;if(pq){for(int il;ir;i){if(a[i]add[pos[i]]x){res;}}}else{for(int il;iR[p];i){if(a[i]add[pos[i]]x){res;}}for(int iL[q];ir;i){ if(a[i]add[pos[i]]x){res;}}for(int ip1;iq-1;i){resbinary(i,x);}}return res;
}
void work(int l,int r){int ppos[l];int qpos[r];for(int ip;iq;i){if(re[i]){rebuild(i);re[i]0;}}
}
inline int kth(int k,int L,int R){if(k1 || R-L1k){return -1;}work(L,R);int res-1;ll lgetmin(L,R),rgetmax(L,R);while(lr){ll mid(lr)1;if(check(L,R,mid)k){//选的值太小lmid1;}else{rmid-1;resmid;}}return res;
}
inline void modify(int l,int r,int k){int ppos[l];int qpos[r];if(pq){for(int il;ir;i){a[i]k;}re[p]1;// rebuild(p);}else{for(int il;iR[p];i){a[i]k;}re[p]1;// rebuild(p);for(int ip1;iq-1;i){add[i]k;}for(int iL[q];ir;i){a[i]k;}re[q]1;// rebuild(q);}
}
int main(){// ios::sync_with_stdio(false);// cin.tie(0),cout.tie(0);int n,m;nread();mread();for(int i1;in;i){a[i]read();}int blosqrt(n);int tceil(1.0*n/blo);for(int i1;it;i){L[i](i-1)*blo1;R[i](it?n:i*blo);}for(int i1;it;i){for(int jL[i];jR[i];j){pos[j]i;}}for(int i1;in;i){v[pos[i]].push_back(a[i]);}for(int i1;it;i){sort(v[i].begin(),v[i].end());}for(int i1;im;i){int op,l,r,k;opread();lread();rread();kread();if(op1){write(kth(k,l,r));putchar(\n);}else{modify(l,r,k);}}return 0;
}
