关键词：
可持久化线段树模板
1.结构体的打法
#include<cstdio> #include<cctype> #include<algorithm> using namespace std; const int maxn=200010; struct dataint l,r,sz;tr[maxn<<5]; int n,m,cnt,key,a[maxn],rk[maxn],id[maxn],rt[maxn]; inline int read(int &x) char ch=getchar();x=0; while(!isdigit(ch))ch=getchar(); while(isdigit(ch))x=(x<<1)+(x<<3)+ch-\'0\';ch=getchar(); bool cmp(const int &x,const int &y) return a[x]<a[y]; void build(int l,int r,int &pos) tr[++cnt]=tr[pos];pos=cnt;tr[cnt].sz++; if(l==r)return; int mid=(l+r)>>1; if(key<=mid)build(l,mid,tr[cnt].l);else build(mid+1,r,tr[cnt].r); int query(int l,int r,int x,int y,int k) if(l==r)return l; int mid=(l+r)>>1,sz=tr[tr[y].l].sz-tr[tr[x].l].sz; if(k<=sz)return query(l,mid,tr[x].l,tr[y].l,k); else return query(mid+1,r,tr[x].r,tr[y].r,k-sz); int main() read(n);read(m); for(int i=1;i<=n;i++)read(a[i]);id[i]=i; sort(id+1,id+n+1,cmp); for(int i=1;i<=n;i++)rk[id[i]]=i; for(int i=1;i<=n;i++) rt[i]=rt[i-1]; key=rk[i];build(1,n,rt[i]); while(m--) int l,r,k;read(l);read(r);read(k); printf("%d\\n",a[id[query(1,n,rt[l-1],rt[r],k)]]);
2.数组打法
#include<cstdio> #include<cctype> #include<algorithm> #define maxn 200005 using namespace std; int n,m,cnt,rt[maxn],rk[maxn]; int l[maxn<<5],r[maxn<<5],siz[maxn<<5],a[maxn],id[maxn]; inline void read(int &x) char ch=getchar();x=0; while(!isdigit(ch))ch=getchar(); while(isdigit(ch))x=(x<<1)+(x<<3)+ch-\'0\';ch=getchar(); inline void buildtr(int &root,int L,int R,int now) l[++cnt]=l[root];r[cnt]=r[root];siz[cnt]=siz[root]+1; root=cnt; if(L==R)return; int mid=(L+R)>>1; if(now<=mid)buildtr(l[cnt],L,mid,now);else buildtr(r[cnt],mid+1,R,now); inline int query(int L,int R,int x,int y,int k) if(L==R)return L; int mid=(L+R)>>1,sz=siz[l[y]]-siz[l[x]]; if(sz>=k)return query(L,mid,l[x],l[y],k);else return query(mid+1,R,r[x],r[y],k-sz); inline bool cmp(int x,int y) return a[x]<a[y]; int main() read(n);read(m); for(int i=1;i<=n;i++)read(a[i]);id[i]=i; sort(id+1,id+n+1,cmp); for(int i=1;i<=n;i++)rk[id[i]]=i; for(int i=1;i<=n;i++) rt[i]=rt[i-1];buildtr(rt[i],1,n,rk[i]); while(m--) int L,R,k;read(L);read(R);read(k);printf("%d\\n",a[id[query(1,n,rt[L-1],rt[R],k)]]);
洛谷u3348a2-回文数
U3348A2-回文数题目背景方方方很喜欢回文数，于是就有了一道关于回文数的题目。题目描述求从小到大第n（1<=n<=10^18）个回文数。注释：出题人认为回文数不包括0。输入输出格式输入格式： 一行一个正整数n。 输出... 查看详情
●洛谷p3348[zjoi2016]大森林
题链：https://www.luogu.org/problemnew/show/P3348题解：LCT，神题 首先有这么一个结论： 每次的1操作（改变生长点操作），一定只会会对连续的一段区间产生影响。 （即不存在对两段不相连的区间都进行了该操作的情况，令这种情况... 查看详情
洛谷u3348a2-回文数
题目背景方方方很喜欢回文数，于是就有了一道关于回文数的题目。题目描述求从小到大第n（1<=n<=10^18）个回文数。注释：出题人认为回文数不包括0。输入输出格式输入格式： 一行一个正整数n。 输出格式： 第n... 查看详情
洛谷u3348a2-回文数
题目背景方方方很喜欢回文数，于是就有了一道关于回文数的题目。题目描述求从小到大第n（1<=n<=10^18）个回文数。注释：出题人认为回文数不包括0。输入输出格式输入格式： 一行一个正整数n。 输出格式： 第n... 查看详情
poj3348cows凸包板子(代码片段)
凸包板子#include<iostream>#include<cstdio>#include<cmath>#include<cstring>#include<algorithm>usingnamespacestd;structPointintx,y;;Pointa[10010];Pointb[10010];boolcmp(Pointa 查看详情
hdu-3348coins(代码片段)
HDU-3348coinsDescription"Yakexi,thisisthebestage!"DongMWworkshardandgethighpay,hehasmany1Jiaoand5Jiaobanknotes(纸币),somedayhewenttoabankandchangespartofhismoneyinto1Yuan,5Yuan,10Yuan.(1Yuan=10Jiao)"Thankstothebestage,Icanbuymanythings!"NowDongMWhasabooktobuy,itcostsPJiao.Hewon... 查看详情
p3348[zjoi2016]大森林（lct）(代码片段)
Luogu3348BZOJ4573DarkBZOJ4573题解对于每个1操作建一个虚点，以后的0操作都连在最近建好的虚点上。这样每次整体嫁接的时候，直接把这个虚点断掉它原来的父亲，再link过去就可以了求在x位置的两点之间距离,只要之前的换点加点操... 查看详情
poj3348cows(代码片段)
简单的求凸多边形面积求不规则多边形也是类似只要选择的点是沿着多边形边选就行了 通过容斥会得到正确答案 #include<cmath>#include<cstdio>#include<algorithm>#definedbdoubleusingnamespacestd;constintN=1e4+50;constdbeps=1e-9;structP... 查看详情
poj3348cows
...求叉乘之和，也就是将凸包分成许多小三角形求面积和。代码：//poj3348#include<algorithm>#include&l 查看详情
●poj3348cows
题链：http://poj.org/problem?id=3348题解：计算几何，凸包，多边形面积好吧，就是个裸题，没什么可讲的。代码：#include<cmath>#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#defineMAXN 查看详情
hdu-3348-coins
...。求这个的最小张数，剩下的则是原本价值的最大张数。代码：#include<iostream>#include<memory.h># 查看详情
洛谷2458(代码片段)
f[now][0]表示以当前点为根，且要取该点，满足条件的最小#include<cstdio>#include<cctype>#include<cstring>#include<algorithm>usingnamespacestd;inthead[1501],to[1501],nex[1501],val[1501],indg[1501],f[150 查看详情
求细胞数量-洛谷(代码片段)
求细胞数量-洛谷法1：BFS#include<iostream>#include<cstdio>usingnamespacestd;intdx[4]=-1,0,1,0;intdy[4]=0,1,0,-1;//左、右、上、下intbz[100][100],num=0,n,m;voiddoit(intp,intq)intx,y,t,w,i; 查看详情
洛谷p1535游荡的奶牛(代码片段)
P1535游荡的奶牛题目描述Searchingfortheverybestgrass,thecowsaretravellingaboutthepasturewhichisrepresentedasagridwithNrowsandMcolumns(2<=N<=100;2<=M<=100).KeenobserverFarmerJohnhasrecordedBessie‘spo 查看详情
洛谷p1816忠诚(代码片段)
https://www.luogu.org/problemnew/show/1816st表模板#include<cstdio>#include<algorithm>usingnamespacestd;typedeflonglongLL;LLm,n;LLa[100100],d[100100][20];intmain()LLi,j,l,r,k;scanf("%lld%lld" 查看详情
一个洛谷material化的stylish主题(代码片段)
一个将洛谷MaterialDesign化的主题。发布在stylish上，地址：https://userstyles.org/styles/157651/material-luogu-material欢迎发送issue截图代码最新代码请到stylish主题页面查看。https://userstyles.org/styles/157651/material-luogu-material@-moz-do 查看详情
洛谷1525关押罪犯——二分(代码片段)
题目：https://www.luogu.org/problemnew/show/P1525二分答案+二分图染色。#include<iostream>#include<cstdio>#include<cstring>usingnamespacestd;typedeflonglongll;intn,m,head[20005],xnt,x,y;llans,l,r,z 查看详情
洛谷1608路径统计(代码片段)
【题解】 最短路计数的模板题吧。。要把重边判掉。。 1#include<cstdio>2#include<algorithm>3#defineN20104#definergregister5usingnamespacestd;6intn,m,tot=0,dis[N],pos[N],last[N],cnt[N],rec[N][N][11];7structedge8int 查看详情