NOIP考前复习模板
钱逸凡
2018-11-09 14:08:46
```
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
const int inf=1<<30;
////////////////////////////////
////////////////////////////////
//读入优化整数
inline long long Read(){
long long x=0,f=1;
char c=getchar();
while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return x*f;
}
//读入优化实数
inline double READ(){
double x=0,f=1;
char c=getchar();
while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
if(c=='.'){
double a=0.1;
c=getchar();
while(c>='0'&&c<='9')x+=a*(c-'0'),c=getchar(),a*=0.1;
}
return x*f;
}
///////////////////////////////////
///////////////////////////////////
const int mx=101010;//数组大小
const int N=101100;//点数
const int M=205050;//边数
///////////////////////////////////////////
///////////////////////////////////////////
//树状数组
struct TREE{
#define lowbit(i) i&-i
long long tree[mx];
int n;
inline void add(int i,int x,long long a[]){
while(i<=n){
a[i]+=x;
i+=lowbit(i);
}
}//单点更新
inline long long querysum(int i,long long a[]){
long long ans=0;
while(i>0){
ans+=a[i];
i-=lowbit(i);
}
return ans;
}
long long c1[mx],c2[mx];//差分数组，差分的差分数组
inline void LRupdate(int l,int r,int x){
add(l,x,c1),add(r+1,-x,c1);
add(l,(l-1)*x,c2),add(r+1,-r*x,c2);
}//区间更新
inline long long queryLR(int l,int r){
long long s1=r*querysum(r,c1)-querysum(r,c2);
long long s2=(l-1)*querysum(l-1,c1)-querysum(l-1,c2);
return s1-s2;
} //区间查询
}T1;
///////////////////////////////////////////
///////////////////////////////////////////
//线段树
struct T{//对应数组
long long val;
long long add;
int l;
int r;
};
struct SegTree{
T tr[mx<<2];
inline void pushdown(int i){
if(tr[i].add){
tr[i<<1].val+=(tr[i<<1].r-tr[i<<1].l+1)*tr[i].add;
tr[i<<1].add+=tr[i].add;
tr[i<<1|1].val+=(tr[i<<1|1].r-tr[i<<1|1].l+1)*tr[i].add;
tr[i<<1|1].add+=tr[i].add;
tr[i].add=0;
}
}
long long a[mx];//原数组
void build(int i,int l,int r){
tr[i].l=l,tr[i].r=r;
if(l==r){
tr[i].val=a[l];
return;
}
int mid=(l+r)>>1;
build(i<<1,l,mid);
build(i<<1|1,mid+1,r);
tr[i].val=tr[i<<1].val+tr[i<<1|1].val;
}
void update(int i,int l,int r,long long x){
if(tr[i].l>r||l>tr[i].r)return;
if(l<=tr[i].l&&tr[i].r<=r){
tr[i].val+=(tr[i].r-tr[i].l+1)*x;
tr[i].add+=x;
return;
}
pushdown(i);
update(i<<1,l,r,x);
update(i<<1|1,l,r,x);
tr[i].val=tr[i<<1].val+tr[i<<1|1].val;
}//[l,r]更新
long long query(int i,int l,int r){
if(tr[i].l>r||l>tr[i].r)return 0;
if(l<=tr[i].l&&tr[i].r<=r)return tr[i].val;
pushdown(i);
return query(i<<1,l,r)+query(i<<1|1,l,r);
}//区间查询
}T2;
////////////////////////////////////////////////////
///////////////////////////////////////////////////
//二叉堆
struct HHeap{//每个堆内的元素
int h;//优先级
int pos;//位置等信息
bool operator > (const HHeap &x){
return h<x.h;//因为后面要写dijstra，所以就用小根堆了
// return h>x.h;//大根堆
}
};
struct Heap{
#define swap(x,y) x^=y^=x^=y
int siz;
HHeap heap[mx];
inline void sswap(HHeap &a,HHeap &b){
swap(a.h,b.h);
swap(a.pos,b.pos);
}
void insert(HHeap a){
heap[++siz]=a;
int fa,now;
now=siz;
while(now){
fa=now>>1;
if(heap[now]>heap[fa])sswap(heap[now],heap[fa]),now=fa;
else break;
}
}//插入x
void pop(){
sswap(heap[siz],heap[1]);
siz--;
int now=1,son;
while((now<<1)<=siz){
son=now<<1;
if(son<siz&&heap[son|1]>heap[son])son|=1;
if(heap[son]>heap[now])sswap(heap[son],heap[now]),now=son;
else break;
}
}
}H;
/////////////////////////////////////
//////////////////////////////////////
////dijstra
struct Dijstra{
int n,m;
int dist[N],vis[N];
int s;//起点
struct Node{
int v;
int val;
int next;
}node[M];
int top,head[N];
Heap h;//堆
inline void addedge(int u,int v,int val){
node[++top].v=v;
node[top].val=val;
node[top].next=head[u];
head[u]=top;
}
void dijstra(){
memset(dist,0x3f,sizeof(dist));
dist[s]=0;
HHeap now;
now.pos=s,now.h=0;
h.insert(now);
while(h.siz){
int u=h.heap[1].pos;
h.pop();
if(vis[u])continue;
vis[u]=1;
for(int i=head[u];i;i=node[i].next){
int d=node[i].v;
if(dist[d]>dist[u]+node[i].val){
dist[d]=dist[u]+node[i].val;
now.pos=d,now.h=dist[d];
h.insert(now);//入堆
}
}
}
}
}D;
/////////////////////////////////////
////////////////////////////////////////
//树链剖分//由于不想写取模，所以过不了板子
struct SLPF{
int n,m;
struct Node{
int v;
int next;
}node[N<<1];
int cnt,head[N];
inline void addedge(int u,int v){
node[++cnt].v=v;
node[cnt].next=head[u];
head[u]=cnt;
}
inline void add(int u,int v){
addedge(u,v);
addedge(v,u);
}
int dep[N],siz[N],fa[N],son[N],top[N];
int T,dfn[N],real[N];
int a[N];
void dfs1(int u){
siz[u]=1;
for(int i=head[u];i;i=node[i].next){
int d=node[i].v;
if(fa[u]!=d){
fa[d]=u;
dep[d]=dep[u]+1;
dfs1(d);
siz[u]+=siz[d];
if(siz[d]>siz[son[u]])son[u]=d;
}
}
}
void dfs2(int u,int tp){
dfn[u]=++T;
real[dfn[u]]=u;
top[u]=tp;
if(son[u])dfs2(son[u],tp);
for(int i=head[u];i;i=node[i].next){
int d=node[i].v;
if(fa[u]!=d&&son[u]!=d)dfs2(d,d);
}
}
void changepath(int u,int v,int x){
while(top[u]!=top[v]){
if(dep[top[u]]>dep[top[v]])swap(u,v);
T2.update(1,dfn[top[v]],dfn[v],x);
v=fa[top[v]];
}
if(dep[u]>dep[v])swap(u,v);
T2.update(1,dfn[u],dfn[v],x);
}
long long querypath(int u,int v){
long long ans=0;
while(top[u]!=top[v]){
if(dep[top[u]]>dep[top[v]])swap(u,v);
ans+=T2.query(1,dfn[top[v]],dfn[v]);
v=fa[top[v]];
}
if(dep[u]>dep[v])swap(u,v);
ans+=T2.query(1,dfn[u],dfn[v]);
return ans;
}
void changetree(int u,int x){
int l=dfn[u];
int r=dfn[u]+siz[u]-1;
T2.update(1,l,r,x);
}
long long querytree(int u){
int l=dfn[u];
int r=dfn[u]+siz[u]-1;
return T2.query(1,l,r);
}
void init(){
n=Read();
register int i;
for(i=1;i<=n;i++) a[i]=Read();
for(i=1;i<n;i++) add(Read(),Read());
dfs1(1);
dfs2(1,1);
for(i=1;i<=n;i++)T2.a[i]=a[real[i]];
T2.build(1,1,n);
}//初始化
int lca(int u,int v){
while(top[u]!=top[v]){
if(dep[top[u]]>dep[top[v]])swap(u,v);
v=fa[top[v]];
}
return dep[u]<dep[v]?u:v;
}
}slpf;
//////////////////////////////////////
//////////////////////////////////////
//左偏树（小根堆）
struct LPT{
struct Tree{
int len;//距离
int h;//优先级
int f;//父亲
int ls,rs;//左右儿子
}t[N];
int merge(int a,int b){
if(a==0||b==0)return a+b;//有一个为空
if(t[a].h>t[b].h)swap(a,b);//小根堆
t[a].rs=merge(t[a].rs,b);
t[t[a].rs].f=a;
if(t[t[a].rs].len>t[t[a].ls].len)swap(t[a].ls,t[a].rs);
t[a].len=t[t[a].rs].len+1;
return a;
}//合并两个堆
void pop(int x){
t[t[x].ls].f=t[t[x].rs].f=0;
merge(t[x].ls,t[x].rs);//合并左右儿子
}//堆顶出堆
int find(int x){
while(t[x].f)x=t[x].f;
return x;
}//查找堆顶
}H2;
//////////////////////////////////
/////////////////////////////////
//线性基
struct Line{
long long b[65];//线性基数组
bool insert(long long val){
register int i;
for(i=63;i>=0;i--){
if((val&((long long)1<<i))!=0){
if(b[i]==0){//最高位为该位的数还没有
b[i]=val;
return 1;
}
val^=b[i];
}
}
return 0;//插入失败
}//插入val
Line merge(const Line &a,const Line &b){
Line s=a;
for(register int i=63;i>=0;i--){
if(b.b[i]){//把一个线性基暴力地插入另一个中
s.insert(b.b[i]);
}
}
return s;
}//合并两个线性基
bool find(long long val){
return !insert(val);
}//val是否在线性基内
long long query_max(){
long long ans=0;
for(int i=63;i>=0;i--){
if((ans^b[i])>ans)ans^=b[i];
}
return ans;
}//查询最大异或和
long long query_min(){
for(int i=0;i<=63;i++)if(b[i])return b[i];
return 0;
}//查询最小异或和
long long query_maxn(long long x){
long long ans=x;
for(int i=63;i>=0;i--){
if((ans^b[i])>ans)ans^=b[i];
}
return ans;
}//查询包含x的最大异或和 (x不在线性基内)
long long query_minn(long long x){
long long ans=x;
for(int i=0;i<=63;i++){
if((ans^b[i])<ans)ans^=b[i];
}
return ans;
}//查询包含x的最小异或和(x不在线性基内)
}L;
///////////////////////////////////////////
//////////////////////////////////////////
//字典树
const int len=1001010;//所有单词包含字母的总数
struct Tire{
int cnt;//字母数
int son[len][26];//以只有小写字母为例
bool end[len];
void insert(char s[]){
int now=0;
int a;
int l=strlen(s);
for(int i=0;i<l;i++){
a=s[i]-'a';
if(son[now][a])now=son[now][a];
else son[now][a]=++cnt,now=cnt;
}
end[now]=1;//标记该单词出现了
}//插入单词
bool find(char s[]){
int now=0;
int a;
int l=strlen(s);
for(int i=0;i<l;i++){
a=s[i]-'a';
if(son[now][a])now=son[now][a];
else return 0;
}
if(end[now])return 1;
return 0;
}//查找某个单词是否出现过
};
////////////////////////////////
////////////////////////////////
//(带修改)莫队
//由于涉及排序，好像不资瓷结构体
int cnt[mx];
int a[mx];//原数组
int ansk[mx];//答案
int cntq,cntc;//询问和修改的次数
int ans;
int n;
int now;//当前处理到了第几个询问
int st;//块的大小
int l,r;//当前询问的左右端点
inline void del(int x){
cnt[a[x]]--;
if(cnt[a[x]]==0)ans--;
}
inline void add(int x){
cnt[a[x]]++;
if(cnt[a[x]]==1)ans++;
}
struct Qu{//询问
int l,r;//每个询问左右端点
int pos;//每个询问位置
int pre;//每个询问最近的修改位置
}qu[mx];
struct C{//修改
int pos;
int color;
}c[mx];
bool cmp(Qu a,Qu b){
if(a.l/st!=b.l/st)return a.l/st<b.l/st;
if(a.r/st!=b.r/st){
if((a.l/st)&1)return a.r<b.r;
else return a.r>b.r;
}
return a.pre<b.pre;
}//带修改莫队排序方式
//bool cmp(Qu a,Qu b){
// if(a.l/st!=b.l/st)return a.l<b.l;
// if((a.l/st)&1)return a.r<b.r;
// return a.r>b.r;
//}//不带修改的莫队排序方式
void change(int i){//第i个询问需要的修改
if(qu[i].r>=c[now].pos&&qu[i].l<=c[now].pos){//本次修改会产生影响
if(--cnt[a[c[now].pos]]==0)ans--;//把该颜色的最后一个拿掉了
if(++cnt[c[now].color]==1)ans++;//第一次出现该颜色
}
swap(a[c[now].pos],c[now].color);
}
int query(int i){//处理第i个询问
while(l<qu[i].l)del(l++);
while(l>qu[i].l)add(--l);
while(r<qu[i].r)add(++r);
while(r>qu[i].r)del(r--);//不带修改的莫队只有前四排
while(now<qu[i].pre)change(++now);
while(now>qu[i].pre)change(now--);
return ans;
}
void init(){
//根据题目描述输入询问和修改
// st=n/sqrt(cntq*2/3);//不带修改的快的大小
st=exp((log(n)+log(cntq))/3);//带修改的块的大小
sort(qu+1,qu+1+cntq,cmp);
for(int i=1;i<=cntq;i++)ansk[qu[i].pos]=query(i);
}
/////////////////////////////////////////////
/////////////////////////////////////////////
//tarjan(缩点与2-sat)
struct Tarjan{
int n,m;
int top,head[N];
struct Node{
int v;
int next;
}node[M];
inline void addedge(int u,int v){
node[++top].v=v;
node[top].next=head[u];
head[u]=top;
}
int Belong[N];//每个点属于哪个强连通分量
int dfn[N],T,low[N];
int st[N];//栈
bool instack[N];//是否在栈中
int sttop;//栈顶
int taj;//强连通分量数
void dfs(int u){
dfn[u]=low[u]=++T;
st[++sttop]=u;
instack[u]=1;
for(int i=head[u];i;i=node[i].next){
int d=node[i].v;
if(dfn[d]==0){
dfs(d);
low[u]=min(low[u],low[d]);
}else if(instack[d])low[u]=min(low[u],low[d]);
}
if(low[u]==dfn[u]){
int now;
taj++;
do{
now=st[sttop--];
instack[now]=0;
Belong[now]=taj;
//在此可以进行累加点权等操作
}while(now!=u);
}
}
Node newnode[M];
int newtop;
int newhead[N];
inline void newaddedge(int u,int v){
newnode[++newtop].v=v;
newnode[newtop].next=newhead[u];
newhead[u]=newtop;
}
void suodian(){
for(int i=1;i<=n;i++)if(dfn[i]==0)dfs(i);
for(int i=1;i<=n;i++){
int u=Belong[i];
for(int j=head[i];j;j=node[j].next){
int d=node[j].v;
int v=Belong[d];
if(u!=v)newaddedge(u,v);
}
}
}
void Two_SAT(){
n=Read(),m=Read();
//[1,n]表示真，[n+1,2n]表示假
for(int i=1;i<=m;i++){
int a,fa,b,fb;
a=Read(),fa=Read(),b=Read(),fb=Read();
addedge(a+(fa^1)*n,b+fb*n);
addedge(b+(fb^1)*n,a+fa*n);
}
for(int i=1;i<=2*n;i++)if(dfn[i]==0)dfs(i);
bool f=1;
for(int i=1;i<=n;i++)if(Belong[i]==Belong[i+n])f=0;
if(f)printf("POSSIBLE\n");
else printf("IMPOSSIBLE\n");
if(f)for(int i=1;i<=n;i++)printf("%d ",Belong[i]>Belong[i+n]);
}
}TJ;
//////////////////////////////////
///////////////////////////////////
//splay
struct Splay{
int son[mx][2],f[mx],siz[mx],key[mx],cnt[mx],root;
int n,sz;//点数，当前有多少数在splay内
inline void update(int x){
if(x)siz[x]=cnt[x]+(son[x][0]?siz[son[x][0]]:0)+(son[x][1]?siz[son[x][1]]:0);
}
inline void clear(int x){siz[x]=key[x]=cnt[x]=son[x][0]=son[x][1]=f[x]=0;}
inline bool get(int x){return son[f[x]][1]==x;}
inline void rotate(int x){
int F=f[x],FF=f[F],WF=get(x),WFF=get(F);
int other=son[x][WF^1];
f[x]=FF;
if(F)son[FF][WFF]=x;
f[F]=x;
son[x][WF^1]=F;
f[other]=F;
son[F][WF]=other;
update(F);
update(x);
}
inline void splay(int x){
for(int F=f[x];(f[x]);rotate(x),F=f[x]){
if(f[F])rotate(get(x)==get(F)?F:x);
}
root=x;
}
void insert(int v){
if(root==0){
sz++;
cnt[sz]=siz[sz]=1;
son[sz][0]=son[sz][1]=f[sz]=0;
key[sz]=v;
root=sz;
return;
}
int now=root,F=0;
while(1){
if(key[now]==v){//已经插入过了
cnt[now]++;
update(now);
update(F);
splay(now);
return;
}
F=now;
now=son[now][key[now]<v];
if(now==0){
++sz;
cnt[sz]=siz[sz]=1;
son[sz][0]=son[sz][1]=0;
f[sz]=F;
son[F][key[F]<v]=sz;
key[sz]=v;
update(F);
splay(sz);
return;
}
}
}//删除v
int find(int v){
int ans=0,now=root;
while(1){
if(key[now]>v)now=son[now][0];
else {
ans+=(son[now][0]?siz[son[now][0]]:0);
if(v==key[now]){
splay(now);
return ans+1;
}
ans+=cnt[now];
now=son[now][1];
}
}
}//查v的排名
int findx(int x){
int now=root;
while(1){
if(son[now][0]&&x<=siz[son[now][0]])now=son[now][0];
else{
int temp=(son[now][0]?siz[son[now][0]]:0)+cnt[now];
if(x<=temp)return key[now];
now=son[now][1];
x-=temp;
}
}
}//查找排名为x的值
//注意查前驱之前要先插入v，查完之后要删除v
inline int query_pre(){
int now=son[root][0];
while(son[now][1])now=son[now][1];
return now;
}//查前驱
inline int query_aft(){
int now=son[root][1];
while(son[now][0])now=son[now][0];
return now;
}//查后继
inline void del(int v){
find(v);//把v旋转到根
if(cnt[root]>1){//不止一个点
cnt[root]--;
update(root);
return;
}
if(son[root][0]==0&&son[root][1]==0){//只有根节点一个点
clear(root);
root=0;
return;
}
if(son[root][0]==0){//只有右子树
int oldroot=root;
root=son[root][1];
f[root]=0;
clear(oldroot);
return;
}
if(son[root][1]==0){//只有左子树
int oldroot=root;
root=son[root][0];
f[root]=0;
clear(oldroot);
return;
}
//有两个子树时：
int newroot=query_pre(),oldroot=root;//用前驱做新根
splay(newroot);//把前驱旋转到根
f[son[oldroot][1]]=root;//经过旋转root==newroot
son[root][1]=son[oldroot][1];
clear(oldroot);
update(root);
}//删除v
}SPLAY;
////////////////////////////////
////////////////////////////////
//LCT
struct LCT{
int n,m;
struct Lct{
int son[2];
int f;//父亲
bool t;//翻转标记
}lct[N];
#define swap(x,y) x^=y^=x^=y
inline void pushdown(int x){
if(lct[x].t){
swap(lct[x].son[0],lct[x].son[1]);
lct[lct[x].son[0]].t^=1;
lct[lct[x].son[1]].t^=1;
lct[x].t=0;
}
}
inline void update(int x){
//视题目而定
}
inline bool get(int x){return lct[lct[x].f].son[1]==x;}
inline bool isroot(int x){return lct[lct[x].f].son[1]!=x&&lct[lct[x].f].son[0]!=x;}
inline void rotate(int x){
int F=lct[x].f,FF=lct[F].f,WF=get(x),WFF=get(F);
int other=lct[x].son[WF^1];
lct[x].f=FF;
if(!isroot(F))lct[FF].son[WFF]=x;
lct[other].f=F;
lct[F].son[WF]=other;
lct[x].son[WF^1]=F;
lct[F].f=x;
update(F);
update(x);
}
int st[mx];//栈
inline void splay(int x){
int top=0,now=x;
st[++top]=now;
while(!isroot(now))now=lct[now].f,st[++top]=now;
while(top)pushdown(st[top--]);
for(int F=lct[x].f;!isroot(x);rotate(x),F=lct[x].f){
if(!isroot(F))rotate(get(x)==get(F)?F:x);
}
}
inline void access(int x){//把x到根的路径改为实链
int pre=0;
while(x){
splay(x);
lct[x].son[1]=pre;
pre=x;
update(x);
x=lct[x].f;
}
}
inline void makeroot(int x){//把x改为根
access(x);
splay(x);
lct[x].t^=1;
}
inline int findroot(int x){//找到x的根
access(x);
splay(x);
pushdown(x);
while(lct[x].son[0])x=lct[x].son[0];//根节点一定是最浅的
return x;
}
inline void spilt(int x,int y){//把x到y的路径放在一根实链上
makeroot(x);
access(y);
splay(y);
}
inline void link(int x,int y){//x与y加边
makeroot(x);
if(findroot(y)!=x)//已经连通就不用加边了
lct[x].f=x;//findroot过程中已经把y旋转到根了
}
inline void cut(int x,int y){//x与y删边
makeroot(x);
if(findroot(y)!=x)return;//不连通就不用删边了
if(lct[x].f!=y||lct[y].son[0]!=x)return;//经过findroot，y成为了根
if(lct[x].son[1])return;//x的右儿子一定是比x深又比y浅的，即在他们之间，他们之间没有边
lct[x].f=0;
lct[y].son[0]=0;
update(y);
}
}LCT_Tree;
//////////////////////////////////
//////////////////////////////////
//线性筛素数
struct Line_Prime{
int Prime[mx];
int o;//当前晒出了几个素数
bool chick[mx];
void solve(int n){//从1到n的素数
register int i,j;
chick[1]=1;
for(i=2;i<=n;i++){
if(chick[i]==0){
Prime[++o]=i;
}
for(j=1;j<=o;j++){
if(i*Prime[j]>n)break;
chick[i*Prime[j]]=1;
if(i%Prime[j]==0)break;
}
}
}
}LineP;
/////////////////////////////////////
//////////////////////////////////////
//主席树
struct ZXTree{
int cnt;//现在有多少个点
int n,m;//n个数，m个询问
int q;//去重后后有多少个点
int l[mx<<5],r[mx<<5],root[mx],siz[mx<<5];
int a[mx],b[mx];//原数组，去重数组
void build(int &t,int ll,int rr){
t=++cnt;
if(ll==rr)return;
int mid=(ll+rr)>>1;
build(l[t],ll,mid);
build(r[t],mid+1,rr);
}//建空树
int insert(int t,int ll,int rr,int p){
int o=++cnt;
l[o]=l[t],r[o]=r[t],siz[o]=siz[t]+1;
if(ll==rr)return o;
int mid=(ll+rr)>>1;
if(p<=mid)l[o]=insert(l[o],ll,mid,p);
else r[o]=insert(r[o],mid+1,rr,p);
return o;
}//插入(去重后)第p大的新节点
int query(int u,int v,int ll,int rr,int k){
if(ll==rr)return ll;
int mid=(ll+rr)>>1,x=siz[l[v]]-siz[l[u]];
if(x>k)return query(l[u],l[v],ll,mid,k);
else return query(r[u],r[v],mid+1,rr,k-x);
}//查询区间[u-1,v]第k小
int twopoint(int x){
int ll=1,rr=q;
int mid;
while(1){
mid=(ll+rr)>>1;
if(b[mid]==x)return mid;
if(b[mid]>x)rr=mid-1;
else ll=mid+1;
}
}//二分出x是去重后第几大（用于插入前的预处理）
void init(){
register int i;
n=Read(),m=Read();
for(i=1;i<=n;i++)a[i]=Read(),b[i]=a[i];
sort(b+1,b+1+n);
q=unique(b+1,b+1+n)-b-1;//去重后一共多少种数
build(r[0],1,q);
for(i=1;i<=n;i++){
//嫌麻烦不想手写二分可以调用stl
//p=lower_bound(b+1,b+1+q,a[i])-b;
root[i]=insert(root[i-1],1,q,twopoint(a[i]));
}
int ll,rr,k;
for(i=1;i<=m;i++){
ll=Read(),rr=Read(),k=Read();
printf("%d\n",b[query(root[ll-1],root[rr],1,q,k)]);
}
}
};
////////////////////////////////
///////////////////////////////
//最小费用最大流（DInic）
struct MINcostMAXflow{
int n,m,s,t;
int maxflow,cost;
int top;
int head[N];
void init(){top=1;}
struct Node{
int v;
int val;
int next;
int w;
}node[M];
inline void addedge(int u,int v,int val,int w){
node[++top].v=v;
node[top].next=head[u];
node[top].w=w;
node[top].val=val;
head[u]=top;
}
inline void add(int u,int v,int val,int w){
addedge(u,v,val,w);
addedge(v,u,0,-w);
}
int inque[N],dist[N],vis[N];
int cur[N];//当前弧
bool spfa(){
for(int i=1;i<=t;i++)cur[i]=head[i],dist[i]=inf;
queue<int>q;
q.push(s);
dist[s]=0;
while(!q.empty()){
int u=q.front();
q.pop();
inque[u]=0;
for(int i=head[u];i;i=node[i].next){
int d=node[i].v;
if(dist[d]>dist[u]+node[i].w){
dist[d]=dist[u]+node[i].w;
if(!inque[d]){
q.push(d);
inque[d]=1;
}
}
}
}
return dist[t]!=inf;
}
int dfs(int u,int flow){
if(u==t){
maxflow+=flow;
return flow;
}
int used=0;
vis[u]=1;
for(int i=head[u];i;i=node[i].next){
int d=node[i].v;
if((vis[d]==0||d==t)&&dist[d]==dist[u]+node[i].w){
int mi=dfs(d,min(node[i].val,flow-used));
if(mi){
node[i].val-=mi;
node[i^1].val+=mi;
cost+=node[i].w*mi;
used+=mi;
if(used==flow)break;
}
}
}
return used;
}
void Dinic(){
while(spfa()){
vis[t]=1;
while(vis[t]){
memset(vis,0,sizeof(vis));
dfs(s,inf);
}
}
}
};
////////////////////////////////
///////////////////////////////////
//并查集
struct BCJ{
int set[mx];
int n;
void init(){
for(int i=1;i<=n;i++)set[i]=i;
}
int find(int x){
return set[x]==x?x:set[x]=find(set[x]);
}
void merge(int x,int y){
int sx=find(x),sy=find(y);
if(sx==sy)return;
if(sx>sy)swap(sx,sy);
set[sy]=sx;
}
};
/////////////////////////////////
////////////////////////////////
//floyd
struct Floyd{
int go[1010][1010];
int n;
void solve(){
int i,j,k;
for(k=1;k<=n;k++){
for(j=1;j<=n;j++){
for(i=1;i<=n;i++){
go[i][j]=min(go[i][j],go[i][k]+go[k][j]);
}
}
}
}
};
////////////////////////////////////////
////////////////////////////////////////
//vector实现平衡树
struct VSplay{
/*一些关于vector的函数
定义：vector<int>a; 需<vector>头文件
访问元素：a[x] 取出a中的第(x+1)个数（下标从0开始 O(1)
a.begin()：返回起始元素的迭代器 O(1)
a.end()：返回终止元素的迭代器 O(1)
a.insert(a.begin()+pos,x)：在第pos个数后面插入x O(n)
a.erase(a.begin()+pos)：删除pos位置的数 pos之后的数自动补齐 O(n)
lower_bound(a.begin(),a.end(),x)返回第一个大于等于x的位置的迭代器 O(logn)
upper_bound(a.begin(),a.end(),x)返回第一个大于x的位置的迭代器(x的后继或x) O(logn)
*it：取出迭代器it中的值*/
vector<int>v;
void insert(int x){//插入x
v.insert(upper_bound(v.begin(),v.end(),x),x);
}
void del(int x){//删除x
v.erase(lower_bound(v.begin(),v.end(),x));
}
int find_kth(int x){//查询x的排名
return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
}
int find_val(int x){//查询排名为x的数
return v[x-1];
}
int find_pre(int x){//查前驱
return *--lower_bound(v.begin(),v.end(),x);
}
int find_aft(int x){//查后继
return *upper_bound(v.begin(),v.end(),x);
}
};
///////////////////////////////////////////
//////////////////////////////////////////////
//高精度
struct Bign{
int len,s[mx];;
Bign(){len=1,memset(s,0,sizeof(s));}
Bign(int num){*this=num;}
Bign(const char *num){*this=num;}
Bign operator = (const int num){
char st[mx];
sprintf(st,"%d",num);
return *this=st;
}
Bign operator = (const char *num){
len=strlen(num);
for(int i=0;i<len;i++)s[i]=num[len-i-1]-'0';
return *this;
}
void clean(){while(len&&s[len-1]==0)len--;}
Bign operator + (const Bign &x){
Bign c;
int l=max(len,x.len);
for(int i=0;i<l;i++){
c.s[i]+=s[i]+x.s[i];
c.s[i+1]+=c.s[i]/10;
c.s[i]%=10;
}
c.len=l+1;
c.clean();
return c;
}
Bign operator - (const Bign &x){
Bign c=*this;
int l=max(len,x.len);
for(int i=0;i<l;i++){
c.s[i]-=x.s[i];
if(c.s[i]<0){
c.s[i+1]--;
c.s[i]+=10;
}
}
c.clean();
return c;
}
Bign operator * (const Bign &b){
Bign c;
for(int i=0;i<len;i++){
for(int j=0;j<b.len;j++){
c.s[i+j]+=s[i]*b.s[j];
c.s[i+j+1]+=c.s[i+j]/10;
c.s[i+j]%10;
}
}
c.len=len+b.len+1;
c.clean();
return c;
}
bool operator > (const Bign &b){
if(len!=b.len)return len>b.len;
for(int i=len-1;i>=0;i--){
if(s[i]!=b.s[i])return s[i]>b.s[i];
}
return 0;//相等
}
string str() const{
string re="";
for(int i=0;i<len;i++)re=(char)(s[i]+'0')+re;
return re;
}
};
istream &operator >> (istream &in,Bign &x){
string s;
cin>>s;
x=s.c_str();
return in;
}
ostream &operator << (ostream &out,const Bign &x){
out<<x.str();
return out;
}
////////////////////////////
////////////////////////////
//矩阵快速幂
const int mod=(1e9)+7;//常见模数
struct MatMul{
struct Mat{
long long mat[101][101];
int n,m;//n行m列的矩阵
Mat(){memset(mat,0,sizeof(mat));n=m=0;}
};
int n;
Mat e;
void init(){for(int i=0;i<=n;i++)e.mat[i][i]=1;}//预处理出单位矩阵
Mat Mul(Mat x,Mat y){//x与y相乘
register int i,j,k1;
if(x.m!=y.n)return e;//必须满足能相乘的条件
Mat out;
int n=x.n;
int k=x.m;
int m=y.m;
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
for(k1=1;k1<=k;k1++){
out.mat[i][j]=(x.mat[i][k1]*y.mat[k1][j]+out.mat[i][j])%mod;
}
}
}
return out;
}
Mat pow(Mat x,long long k){//x矩阵的k次方
Mat ans=e;
Mat base=x;
while(k){
if(k&1)ans=Mul(ans,base);
base=Mul(base,base);
k>>=1;
}
return ans;
}
};
//////////////////////////
//////////////////////////
//背包
struct BackPack{
int dp[101010];//滚动数组
int n,W;//物品总数，总重量
int val[101010];//每个物品的价值
int w[101010];//每个物品的重量
void solve_01(){//01背包
int i,j;
for(i=0;i<=n;i++){
for(j=W;j>=w[i];j--){//倒序循环防止多取
dp[j]=max(dp[j],dp[j-w[i]]+val[i]);
}
}
printf("%d",dp[W]);
}
void solve_CM(){//完全背包
int i,j;
for(i=0;i<=n;i++){
for(j=w[i];j<=W;j++){//正序循环可以多取
dp[j]=max(dp[j],dp[j-w[i]]+val[i]);
}
}
printf("%d",dp[W]);
}
};
////////////////////////////////
///////////////////////////////
//扩展欧几里得
struct EXGCD{
void exgcd(int a,int b,int &d,int &x,int &y){
if(!b){
d=a;x=1;y=0;
}
else{
exgcd(b,a%b,d,y,x);//输入时要保证a>b否则会死循环
y-=x*(a/b);
}
}//求解ax+by==gcd(a,b)，d为最大公因数，x，y为对应系数
};
////////////////////////////
////////////////////////////
//大概复习完了吧
int main(){
int noip_2018_score=0;
while(noip_2018_score<=600)noip_2018_score++;
printf("Your will AK noip 2018 TG");
int noip_2018_rp=0;
while(1)noip_2018_rp++;
return 0;
}
```
学OI以来打过最长的代码（第一个比无限之环还长的代码）