上海网站建设最好的公司,北京平面设计公司排行,源码商城网站源码,flash 好的网站正题
题目链接#xff1a;https://www.luogu.com.cn/problem/P3332 题目大意
开始nnn个可以重复的集合#xff0c;要求支持操作 1lrc:1\ l\ r\ c:1 l r c:将ccc加入集合l∼rl\sim rl∼r中2lrk:2\ l\ r\ k:2 l r k:查询l∼rl\sim rl∼r的并集中第kkk大的数 解题思路
此题考…正题
题目链接https://www.luogu.com.cn/problem/P3332 题目大意
开始nnn个可以重复的集合要求支持操作
1lrc:1\ l\ r\ c:1 l r c:将ccc加入集合l∼rl\sim rl∼r中2lrk:2\ l\ r\ k:2 l r k:查询l∼rl\sim rl∼r的并集中第kkk大的数 解题思路
此题考验选手的卡常能力
维护一个树套树外面是一个权值线段树然后每个节点套一个区间线段树。然后每次询问和修改的时候就只用使用该节点的线段树的l∼rl\sim rl∼r段即可。
然后区间线段树需要临时开点废话
之后卡常的话用固定标记标记不下传查询的时候再根据沿路的标记来计算答案即可。 codecodecode
#pragma GCC optimize(2)
%:pragma GCC optimize(3)
%:pragma GCC optimize(Ofast)
%:pragma GCC optimize(inline)
%:pragma GCC optimize(-fgcse)
%:pragma GCC optimize(-fgcse-lm)
%:pragma GCC optimize(-fipa-sra)
%:pragma GCC optimize(-ftree-pre)
%:pragma GCC optimize(-ftree-vrp)
%:pragma GCC optimize(-fpeephole2)
%:pragma GCC optimize(-ffast-math)
%:pragma GCC optimize(-fsched-spec)
%:pragma GCC optimize(unroll-loops)
%:pragma GCC optimize(-falign-jumps)
%:pragma GCC optimize(-falign-loops)
%:pragma GCC optimize(-falign-labels)
%:pragma GCC optimize(-fdevirtualize)
%:pragma GCC optimize(-fcaller-saves)
%:pragma GCC optimize(-fcrossjumping)
%:pragma GCC optimize(-fthread-jumps)
%:pragma GCC optimize(-funroll-loops)
%:pragma GCC optimize(-fwhole-program)
%:pragma GCC optimize(-freorder-blocks)
%:pragma GCC optimize(-fschedule-insns)
%:pragma GCC optimize(inline-functions)
%:pragma GCC optimize(-ftree-tail-merge)
%:pragma GCC optimize(-fschedule-insns2)
%:pragma GCC optimize(-fstrict-aliasing)
%:pragma GCC optimize(-fstrict-overflow)
%:pragma GCC optimize(-falign-functions)
%:pragma GCC optimize(-fcse-skip-blocks)
%:pragma GCC optimize(-fcse-follow-jumps)
%:pragma GCC optimize(-fsched-interblock)
%:pragma GCC optimize(-fpartial-inlining)
%:pragma GCC optimize(no-stack-protector)
%:pragma GCC optimize(-freorder-functions)
%:pragma GCC optimize(-findirect-inlining)
%:pragma GCC optimize(-fhoist-adjacent-loads)
%:pragma GCC optimize(-frerun-cse-after-loop)
%:pragma GCC optimize(inline-small-functions)
%:pragma GCC optimize(-finline-small-functions)
%:pragma GCC optimize(-ftree-switch-conversion)
%:pragma GCC optimize(-foptimize-sibling-calls)
%:pragma GCC optimize(-fexpensive-optimizations)
%:pragma GCC optimize(-funsafe-loop-optimizations)
%:pragma GCC optimize(inline-functions-called-once)
%:pragma GCC optimize(-fdelete-null-pointer-checks)
#includecstdio
#includecstring
#includealgorithm
#define ll long long
#define rint register int
using namespace std;
const int M5e410,N(5e4)*40010;
int n,m,tot,cnt,b[M],op[M],l[M],r[M],a[M];
int ls[N],rs[N],lazy[N],root[M*2];
ll val[N];
char buf[123],*headbuf;//fread优化
inline int read(){int x0,y0;char chgetchar();while(ch0||ch9){if(ch-)y1;chgetchar();}while(ch0ch9)x(x1)(x3)(ch^48),chgetchar();return y?-x:x;
}
templatetypename T
inline T read(){T x0;int y0;char chgetchar();while(ch0||ch9){if(ch-)y1;chgetchar();}while(ch0ch9)x(x1)(x3)(ch^48),chgetchar();return y?-x:x;
}
void print(int x){if(x0)putchar(-),x-x;if(x9)print(x/10);putchar(x%1048);
}
inline void updata(int x,int l,int r,int L1,int Rn){if(!x)xcnt;val[x](ll)(min(R,r)-max(L,l)1);if(lLRr){lazy[x];return;}rint mid(LR)1;if(midl)updata(ls[x],l,r,L,mid);if(rmid)updata(rs[x],l,r,mid1,R);return;
}
inline ll ask(int x,int l,int r,int L1,int Rn,ll t0){if(!x) return (ll)(min(R,r)-max(L,l)1)*t;if(lLRr)return val[x]1ll*(min(R,r)-max(L,l)1)*t;rint mid(LR)1;ll ans0;if(midl)ansask(ls[x],l,r,L,mid,tlazy[x]);if(rmid)ansask(rs[x],l,r,mid1,R,tlazy[x]);return ans;
}
inline void change(int l,int r,int pos,int L1,int Rtot,int x1){updata(root[x],l,r);if(LR)return;rint mid(LR)1;if(posmid)change(l,r,pos,L,mid,x1);else change(l,r,pos,mid1,R,x1|1);return;
}
inline int query(int l,int r,ll k,int L1,int Rtot,int x1){if(LR)return b[L];rint mid(LR)1;ll zask(root[x1|1],l,r);if(zk)return query(l,r,k-z,L,mid,x1);return query(l,r,k,mid1,R,x1|1);
}
int main()
{freopen(P3332_6.in,r,stdin);freopen(P3332_6.ans,w,stdout); nread();mread();for(rint i1;im;i){op[i]read();l[i]read();r[i]read();a[i]read();if(op[i]1)b[tot]a[i];}sort(b1,b1tot);totunique(b1,b1tot)-b-1;for(rint i1;im;i){if(op[i]1)a[i]lower_bound(b1,b1tot,a[i])-b,change(l[i],r[i],a[i]);if(op[i]2)print(query(l[i],r[i],a[i])),putchar(\n);}return 0;
}
