提供商城网站建设,如何做好网站的建设与维护,海晏网站建设公司,网站正在建设中请稍后P3332 [ZJOI2013]K大数查询
题意: 题解#xff1a;
利用整体二分来做#xff0c;这个题和P3834 【模板】可持久化线段树 2的区别在于本题的修改是区间修改#xff0c;所以将里面的树状数组改成线段树就行#xff0c;区间修改区间查询 但是不知道为什么我调了一阵子也不对…P3332 [ZJOI2013]K大数查询
题意: 题解
利用整体二分来做这个题和P3834 【模板】可持久化线段树 2的区别在于本题的修改是区间修改所以将里面的树状数组改成线段树就行区间修改区间查询 但是不知道为什么我调了一阵子也不对。。人傻了
代码
自己写的代码还没调出
#includebits/stdc.h
#define debug(a,b) printf(%s %d\n,a,b)
typedef long long ll;
using namespace std;inline int read(){int s0,w1;char chgetchar();while(ch0||ch9){if(ch-)w-1;chgetchar();}while(ch0ch9) ss*10ch-0,chgetchar();//s(s3)(s1)(ch^48);return s*w;
}
const int maxn5e49;
struct node{int op,x,y;ll k;int id;
}q[maxn],q1[maxn],q2[maxn];
ll ans[maxn];
struct tree{int l,r;ll sum;ll lazy;
}tr[maxn2];
void pushup(int root){tr[root].sumtr[root1].sumtr[root1|1].sum;
}
void cal(int root,ll x)
{tr[root].sum1ll*(tr[root].r-tr[root].l1)*x;tr[root].lazyx;
}
void pushdown(int root){cal(root1,tr[root].lazy);cal(root1|1,tr[root].lazy);tr[root].lazy0;
}
void build(int root,int l,int r)
{tr[root].ll;tr[root].rr;if(lr){tr[root].sum0;tr[root].lazy0;return; }int midlr1;build(root1,l,mid);build(root1|1,mid1,r);pushup(root);
}
void update(int root,int l,int r,ll x){if(tr[root].rl||tr[root].lr)return ;if(tr[root].lltr[root].rr){cal(root,x);return ;}if(tr[root].lazy)pushdown(root);update(root1,l,r,x);update(root1|1,l,r,x);pushup(root);
}
ll query(int root,int l,int r)
{if(tr[root].rl||tr[root].lr)return 0;if(tr[root].lltr[root].rr){return tr[root].sum;}if(tr[root].lazy)pushdown(root);return query(root1,l,r)query(root1|1,l,r);
}void solve(int ql,int qr,ll L,ll R)
{//printf(ql%d qr%d L%d R%d\n,ql,qr,L,R);if(qlqr||LR)return ;if(LR){for(int iql;iqr;i)if(q[i].op2)ans[q[i].id]L;return ;}int len10,len20;ll midLR1;for(int iql;iqr;i){if(q[i].op1)//添加 {if(q[i].kmid)//放在右侧 {q2[len2]q[i];}else{update(1,q[i].x,q[i].y,1);q1[len1]q[i];} }else //查询 {ll tmpquery(1,q[i].x,q[i].y);if(tmpq[i].k){q1[len2]q[i];}else {q[i].k-tmp;q2[len2]q[i];}}}for(int i1;ilen1;i){if(q[i].op1q[i].kmid)update(1,q[i].x,q[i].y,-1);}for(int i1;ilen1;i)q[qli-1]q1[i];for(int i1;ilen2;i)q[qllen1i-1]q2[i];solve(ql,qllen1-1,L,mid);solve(qllen1,qr,mid1,R);
}
int main()
{int n,m;cinnm;int tot0;for(int i1;im;i){int op,l,r;ll c;cinoplrc;if(op1)//添加操作 q[i](node){op,l,r,c};if(op2)//查询 q[i](node){op,l,r,c,tot};}build(1,1,n); solve(1,m,-n,n);for(int i1;itot;i){coutans[i]endl;}return 0;
}
别人的AC的代码和我写的风格很像
#include bits/stdc.h
using namespace std;
#define debug(...) fprintf(stderr,__VA_ARGS__)
typedef long long ll;
const int MAXN200010;
const ll INF2e18;
struct seg{int l,r;ll add,sum;
}t[MAXN2];
void pushup(int x){t[x].sumt[x1].sumt[x1|1].sum;
}
void pushdown(int x){if (!t[x].add) return;int lt[x].l,rt[x].r,mid(lr)1;t[x1].addt[x].add;t[x1|1].addt[x].add;t[x1].sumt[x].add*(mid-l1);t[x1|1].sumt[x].add*(r-mid);t[x].add0;
}
void build(int x,int l,int r){t[x](seg){l,r,0,0};if (lr)return;int mid(lr)1;build(x1,l,mid);build(x1|1,mid1,r);pushup(x);
}
void update(int x,int ql,int qr,ll v){int lt[x].l,rt[x].r;if (qllrqr){t[x].addv;t[x].sumv*(r-l1);return;}pushdown(x);int mid(lr)1;if (qlmid) update(x1,ql,qr,v);if (midqr) update(x1|1,ql,qr,v);pushup(x);
}
ll query(int x,int ql,int qr){int lt[x].l,rt[x].r;if (qllrqr) return t[x].sum;pushdown(x);int mid(lr)1;ll res0;if (qlmid) resquery(x1,ql,qr);if (midqr) resquery(x1|1,ql,qr);return res;
}
ll ans[MAXN];
int n,m;
struct event{int opt,x,y;ll v;int id;void print(){debug(%d %d %d %lld\n,opt,x,y,v);}
}q[MAXN],q1[MAXN],q2[MAXN];
void solve(ll l,ll r,int ql,int qr){if (qlqr||lr) return;if (lr){for (int iql;iqr;i)if (q[i].opt2) ans[q[i].id]l;return;}ll mid(lr)1;int cnt10,cnt20;for (int iql;iqr;i){if (q[i].opt1){if (q[i].vmid){update(1,q[i].x,q[i].y,1);q1[cnt1]q[i];}elseq2[cnt2]q[i];}else{ll tmpquery(1,q[i].x,q[i].y);if (tmpq[i].v)q1[cnt1]q[i];else{q[i].v-tmp;q2[cnt2]q[i];}}}for (int i1;icnt1;i)if (q1[i].opt1q1[i].vmid) update(1,q1[i].x,q1[i].y,-1);for (int iql;iqlcnt1;i)q[i]q1[i-ql1];for (int iqlcnt1;iqr;i)q[i]q2[i-ql-cnt11];solve(mid1,r,ql,qlcnt1-1);solve(l,mid,qlcnt1,qr);
}
int main(){scanf(%d%d,n,m);build(1,1,n);int tot0;for (int i1;im;i){int opt,a,b;ll c;scanf(%d%d%d%lld,opt,a,b,c);if(opt2)q[i](event){opt,a,b,c,tot};else q[i](event){opt,a,b,c,0};}solve(-n,n,1,m);for (int i1;itot;i)printf(%lld\n,ans[i]);return 0;
}
