模板库

犯过的一些傻逼错误

非常重要

  1. 字符串打印的时候,打印了末尾以后的一个字符,这个字符在屏幕显示上是空的所以以为是对的,交上去是0分,因为这个字符是越界的非法字符。一定要注意,因为很多时候调试都是直接打印到stdout的,这样很容易就爆零了。
  2. fft要用两次的时候,特别是两次大小不同的时候,用完了要清空数组。
  3. dp数组开的long long,结果松弛的时候临时变量是int,溢出成狗,满分变30。
  4. 网络流连边时特判一些情况(比如加起来是质数,要特判1和1加在一起连边的情况)。

模拟赛的时候犯的傻逼错,考试不要紧张,每场考试只是oi生涯的一部分,不要剩下10分钟还在对拍,万一犯傻逼错就不太好啊。

  1. 读入优化写错,怎么写错的呢?template,typename T
    • return没有改引用值,不过这个应该测样例就发现的了
    • 明明是可以读long long等的模板,读数的变量写成了int
  2. 输出优化写错,怎么写错的呢?
    • 负数,输出’-‘了以后,没有把负数改成正数,或者脑残直接return了
  3. 写错读写文件:

    • freopen(“xx.out”,”w”,stdin);

      常见到了最后几分钟才交,手忙脚乱直接复制了读入,没改后面的,而且编译通过了。

    • 写错名字,打错freopen
    • 解决办法:剩余10分钟的时候开始准备交,一定要搞个文件读着看看,不要慌。

数据结构

线段树

太多操作了 碰到大杂烩的题就放过来吧

加操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=200000+5;
inline ll readll()
{
char c;ll x=1,tmp=0;c=getchar();
while(!isdigit(c)){if(c=='-') x=-1;c=getchar();}
while(isdigit(c)){tmp=tmp*10+c-'0';c=getchar();}
return tmp*x;
}
ll sumv[maxn*10],addv[maxn*10],a[maxn],n,m,x[maxn],y[maxn];
#define mid l+(r-l)/2
#define lson o*2
#define rson o*2+1
void getadd(int o,int l,int r,ll ad){addv[o]+=ad;sumv[o]+=ad*(r-l+1);}
void maintain(int o,int l,int r){sumv[o]=sumv[lson]+sumv[rson]+addv[o]*(r-l+1);}
void pushdown(int o,int l,int r)
{
if(addv[o]!=0)
{
getadd(lson,l,mid,addv[o]);
getadd(rson,mid+1,r,addv[o]);
addv[o]=0;
maintain(o,l,r);
}
}
void update(int o,int l,int r ,int ql,int qr,ll ad)
{
if(ql>r || qr<l) return;
if(ql<=l && r<=qr) {getadd(o,l,r,ad);return;}
pushdown(o,l,r);
if(ql<=mid) update(lson,l,mid,ql,qr,ad);
if(qr>mid) update(rson,mid+1,r,ql,qr,ad);
maintain(o,l,r);
}
ll query(int o,int l,int r,int ql,int qr)
{
if(ql>r || qr<l) return 0;
if(ql<=l && r<=qr) return sumv[o];
pushdown(o,l,r);
ll sum=0;
if(ql<=mid) sum+=query(lson,l,mid,ql,qr);
if(qr>mid) sum+=query(rson,mid+1,r,ql,qr);
return sum;
}
int main()
{
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++) update(1,1,n,i,i,readll());
int op,l,r;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&op,&l,&r);
if(op==2){
printf("%lld\n",query(1,1,n,l,r));
}else{
ll num=readll();
update(1,1,n,l,r,num);
}
}
return 0;
}

区间乘

bzoj1798[ahoi2009]维护序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T> inline T readin(T &rt)
{
char c;T tmp=0,x=1;c=getchar();
while(!isdigit(c)){if(c=='-') x=-1;c=getchar();}
while(isdigit(c)){tmp=tmp*10+c-'0';c=getchar();}
return rt=tmp*x;
}
template<typename T> inline void writeout(T wt)
{
if(wt==0) {putchar('0');return;}
if(wt<0){wt=-wt;putchar('-');}
static char s[25];int top=0;
while(wt>0){
s[++top]=('0'+wt%10);wt/=10;
}
while(top) putchar(s[top--]);
}
const int maxn=100000+5;
int mo,n,m,a[maxn];
#define lson (o<<1)
#define rson ((o<<1)|1)
struct segment_tree{
ll sumv[maxn*6],addv[maxn*6],mulv[maxn*6];
inline void ini() {for(int i=0;i<maxn*6;i++) mulv[i]=1;}
inline void maintain(int o,int l,int r){sumv[o]=(sumv[lson]+sumv[rson])%mo;}
inline void pushdown(int o,int l, int r)
{
int mid=(l+r)>>1;
mulv[lson]=mulv[lson]*mulv[o]%mo,mulv[rson]=mulv[rson]*mulv[o]%mo;
addv[lson]=(addv[lson]*mulv[o]+addv[o])%mo,addv[rson]=(addv[rson]*mulv[o]+addv[o])%mo;
sumv[lson]=((sumv[lson]*mulv[o])%mo+addv[o]*(mid-l+1))%mo,sumv[rson]=((sumv[rson]*mulv[o])%mo+addv[o]*(r-mid))%mo;
mulv[o]=1,addv[o]=0;
}
inline void build(int o,int l,int r)
{
if(l>r) return;
if(l==r) {sumv[o]=a[l];return;}
else{
int mid=(l+r)>>1;
build(lson,l,mid),build(rson,mid+1,r);
sumv[o]=sumv[lson]+sumv[rson];
}
}
inline void Add(int o,int l,int r,int ql,int qr,ll val)
{
if(ql>r || qr<l) return;
if(ql<=l && r<=qr) {
addv[o]=(addv[o]+val)%mo;
sumv[o]=(sumv[o]+val*1ll*(r-l+1)%mo)%mo;
return;
}else{
int mid=(l+r)>>1;
pushdown(o,l,r);
if(ql<=mid) Add(lson,l,mid,ql,qr,val);
if(qr>mid) Add(rson,mid+1,r,ql,qr,val);
maintain(o,l,r);
}
}
inline void Mul(int o,int l,int r,int ql,int qr,ll val)
{
if(ql>r || qr<l) return;
if(ql<=l && r<=qr) {
addv[o]=addv[o]*val%mo;
mulv[o]=mulv[o]*val%mo;
sumv[o]=sumv[o]*val%mo;
return;
}else{
int mid=(l+r)>>1;
pushdown(o,l,r);
if(ql<=mid) Mul(lson,l,mid,ql,qr,val);
if(qr>mid) Mul(rson,mid+1,r,ql,qr,val);
maintain(o,l,r);
}
}
inline ll Qsum(int o,int l,int r,int ql,int qr)
{
if(ql>r || qr<l) return 0;
if(ql<=l && r<=qr) return sumv[o];
else{
int mid=(l+r)>>1;
ll ret=0;
pushdown(o,l,r);
if(ql<=mid) ret=(ret+Qsum(lson,l,mid,ql,qr))%mo;
if(qr>mid) ret=(ret+Qsum(rson,mid+1,r,ql,qr))%mo;
return ret;
}
}
} Tree;
int main()
{
Tree.ini();
readin(n),readin(mo);
for(register int i=1;i<=n;i++) readin(a[i]);
Tree.build(1,1,n);
readin(m);
int op,l,r;ll tar;
for(register int i=1;i<=m;i++) {
readin(op),readin(l),readin(r);
if(op==1){
readin(tar);
Tree.Mul(1,1,n,l,r,tar);
}else if(op==2){
readin(tar);
Tree.Add(1,1,n,l,r,tar);
}else{
writeout(Tree.Qsum(1,1,n,l,r));puts("");
}
}
return 0;
}

Fenwick树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int sum[maxn];
inline int lowbit(int x){return x&(-x);}
void add(int pos,int ad)
{
while(pos<=n){
sum[pos]+=ad;
pos+=lowbit(pos);
}
}
int getsum(int pos)
{
int ret=0;
while(pos>0){
ret+=sum[pos];
pos-=lowbit(pos);+
}
return ret;
}

Treap

旋转treap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
//la5635
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cassert>
#include <stack>
using namespace std;
const int maxm=3000000+5;
struct node{
int v,r,siz;
node* ch[2];
void maintain()
{
int s=1;
if(ch[0]!=NULL) s+=ch[0]->siz;
if(ch[1]!=NULL) s+=ch[1]->siz;
siz=s;
}
node(int x){
this->v=x;
this->r=rand();
this->siz=1;
this->ch[0]=this->ch[1]=NULL;
}
int cmp(int x)
{
if(x==v) return -1;
else{
return x<v?0:1;
}
}
};
node* rt;
void rotate(node* &o,int d)
{
node* k=o->ch[d^1];
o->ch[d^1]=k->ch[d];
k->ch[d]=o;
o->maintain();
k->maintain();
o=k;
}
void insert(node* &o,int x)
{
if(o==NULL){
o=new node(x);
return;
}
else{
int d=x<o->v?0:1;
insert(o->ch[d],x);
if(o->ch[d]->r > o->r) rotate(o,d^1);
o->maintain();
}
}
int kth(node* &o,int k)
{
if(o==NULL || o->siz<k || k==0) return -1;
int s=o->ch[0]==NULL?0:o->ch[0]->siz;
if(k==s+1) return o->v;
else if(k<=s) return kth(o->ch[0],k);
else return kth(o->ch[1],k-s-1);
}
void print(node* &o)
{
if(o==NULL) return;
if(o->ch[0]!=NULL) print(o->ch[0]);
printf("v=%d r=%d siz=%d || ",o->v,o->r,o->siz);
if(o->ch[1]!=NULL) print(o->ch[1]);
}
int n,m;
int a[maxm],u[maxm];
stack<int > req;
int kas=0;
int main()
{
scanf("%d",&kas);
for(int z=0;z<kas;z++)
{
if(z>=1) puts("");
memset(a,0,sizeof(a));
memset(u,0,sizeof(u));
rt=NULL;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=m;i++) scanf("%d",&u[i]);
for(int i=m;i>=1;i--) req.push(u[i]);
int rnk=0;
for(int i=1;i<=n;i++)
{
insert(rt,a[i]);
while(req.size() && rt->siz==req.top()){
req.pop();
rnk++;
printf("%d\n",kth(rt,rnk));
}
}
}
return 0;
}

fhq treap

普通平衡树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <bits/stdc++.h>
using namespace std;
const int maxn=10*100000+5;
int prio[maxn],val[maxn],ch[maxn][2],siz[maxn];
int n,SIZ=0;
int rd=1,mo=2147483647,Base=19260817;
int getrand()
{
rd=(rd*Base+1)&mo;
return rd;
}
void pushup(int now){siz[now]=siz[ch[now][0]]+1+siz[ch[now][1]];}
int newnode(int valu)
{
siz[++SIZ]=1;
val[SIZ]=valu;
prio[SIZ]=getrand();
return SIZ;
}
int merge(int x,int y)
{
if(!x || !y) return x+y;
else{
if(prio[x]<prio[y]){
ch[y][0]=merge(x,ch[y][0]);
pushup(y);
return y;
}else{
ch[x][1]=merge(ch[x][1],y);
pushup(x);
return x;
}
}
}
void split(int now,int k,int &x,int &y)
{
if(!now) x=y=0;
else{
if(val[now]<=k)
x=now,split(ch[now][1],k,ch[now][1],y);
else
y=now,split(ch[now][0],k,x,ch[now][0]);
pushup(now);
}
}
int kth(int now,int k)
{
while(1){
if(k<=siz[ch[now][0]]) now=ch[now][0];
else if(k==siz[ch[now][0]]+1) return now;
else k-=siz[ch[now][0]]+1,now=ch[now][1];
}
}
int rt=0;
void out(int now)
{
if(!now) return;
out(ch[now][0]);
printf("val[%d]=%d prio[%d]=%d siz[%d]=%d\n",
now,val[now],now,prio[now],now,siz[now]);
out(ch[now][1]);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++){
int op,x;
scanf("%d%d",&op,&x);
if(op==1){
int lef=0,rgh=0;
split(rt,x,lef,rgh);
rt=merge(merge(lef,newnode(x)),rgh);
}else if(op==2){
int lef=0,rgh=0,lrgh=0;
split(rt,x,lef,rgh);
split(lef,x-1,lef,lrgh);
lrgh=merge(ch[lrgh][0],ch[lrgh][1]);
rt=merge(merge(lef,lrgh),rgh);
}else if(op==3){
int lef=0,rgh=0;
split(rt,x-1,lef,rgh);
printf("%d\n",siz[lef]+1);
rt=merge(lef,rgh);
}else if(op==4){
printf("%d\n",val[kth(rt,x)]);
}else if(op==5){
int lef=0,rgh=0;
split(rt,x-1,lef,rgh);
printf("%d\n",val[kth(lef,siz[lef])]);
rt=merge(lef,rgh);
}else{
int lef=0,rgh=0;
split(rt,x,lef,rgh);
printf("%d\n",val[kth(rgh,1)]);
rt=merge(lef,rgh);
}
}
return 0;
}

文艺平衡树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <bits/stdc++.h>
using namespace std;
const int maxn=5*100000+5;
int SIZ=0,rt=0,n,m,siz[maxn],val[maxn],prio[maxn],rev[maxn],ch[maxn][2];
int rd=1,Base=19260817,mo=2147483647;
int getrand()
{
rd=(rd*Base+1)&mo;
return rd;
}
int newnode(int valu)
{
val[++SIZ]=valu;
prio[SIZ]=getrand();
siz[SIZ]=1;
rev[SIZ]=0;
return SIZ;
}
void pushup(int now){siz[now]=1+siz[ch[now][0]]+siz[ch[now][1]];}
void pushdown(int now)
{
if(now && rev[now]){
rev[now]=0;
swap(ch[now][0],ch[now][1]);
if(ch[now][0]) rev[ch[now][0]]^=1;
if(ch[now][1]) rev[ch[now][1]]^=1;
}
}
int merge(int x,int y)
{
if(!x || !y) return x+y;
pushdown(x),pushdown(y);
if(prio[x]<prio[y]){
ch[y][0]=merge(x,ch[y][0]);
pushup(y);
return y;
}else{
ch[x][1]=merge(ch[x][1],y);
pushup(x);
return x;
}
}
void split(int now,int k,int &x,int &y)
{
if(!now) x=y=0;
else{
pushdown(now);
if(k<=siz[ch[now][0]])
y=now,split(ch[now][0],k,x,ch[now][0]);
else x=now,split(ch[now][1],k-siz[ch[now][0]]-1,ch[now][1],y);
pushup(now);
}
}
int kth(int now,int k)
{
while(1){
if(k<=siz[ch[now][0]]) now=ch[now][0];
else if(k==siz[ch[now][0]]+1) return now;
else k-=siz[ch[now][0]],now=ch[now][1];
}
}
int build(int l,int r)
{
if(l>r) return 0;
int mid=(l+r)>>1;
int now=newnode(mid);
ch[now][0]=build(l,mid-1);
ch[now][1]=build(mid+1,r);
pushup(now);
return now;
}
void dfs(int now)
{
if(!now) return;
pushdown(now);
dfs(ch[now][0]);
if(val[now]>=1 && val[now]<=n) printf("%d ",val[now]);
dfs(ch[now][1]);
}
void getrev(int l,int r)
{
int a=0,b=0,c=0,d=0;
split(rt,r,a,b);
split(a,l-1,c,d);
rev[d]^=1;
rt=merge(merge(c,d),b);
}
int main()
{
scanf("%d%d",&n,&m);
rt=build(1,n);
for(int i=1;i<=m;i++){
int l,r;
scanf("%d%d",&l,&r);
getrev(l,r);
}
dfs(rt);
puts("");
return 0;
}

旋转splay

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=(int)1e5+5;
int n,m,a[maxn];
struct node{
int x,siz;
node* ch[2];
void maintain()
{
siz=1;
assert(ch[0]!=NULL);
siz+=ch[0]->siz;
assert(ch[1]!=NULL);
siz+=ch[1]->siz;
}
int cmp(int x)
{
if(x==ch[0]->siz+1) return -1;
else return x<=ch[0]->siz?0:1;
}
} *rt,pool[maxn],*point,*null;
node* newnode(int x)
{
point->x=x;point->siz=1;
point->ch[0]=point->ch[1]=null;
return point++;
}
void init()
{
point=pool;
null=newnode(0);null->siz=0;
rt=newnode(-inf);rt->ch[1]=newnode(inf);
rt->maintain();
}
void rotate(node* &o,int d)
{
node* k=o->ch[d^1];
o->ch[d^1]=k->ch[d];
k->ch[d]=o;
o->maintain();
k->maintain();
o=k;
}
void splay(node* &o,int k)
{
int d=o->cmp(k);
if(d==1) k-=o->ch[0]==null?1:o->ch[0]->siz+1;
if(d!=-1){
node* &p=o->ch[d];
int d2=p->cmp(k);
if(d2==1) k-=p->ch[0]==null?1:p->ch[0]->siz+1;
if(d2!=-1) {
splay(p->ch[d2],k);
if(d==d2) rotate(o,d^1);
else rotate(o->ch[d],d2^1);
}
rotate(o,d^1);
}
}
node* &range(int l,int r)
{
splay(rt,l-1);
splay(rt->ch[1],r-l+1);
return rt->ch[1]->ch[0];
}
int leq(node* o,int x)
{
if(o==null) return 0;
if(o->x>x) return leq(o->ch[0],x);
else return 1+(o->ch[0]==null?0:o->ch[0]->siz)+leq(o->ch[1],x);
}
int le(node* o,int x)
{
if(o==null) return 0;
if(o->x>=x) return le(o->ch[0],x);
else return 1+(o->ch[0]==null?0:o->ch[0]->siz)+le(o->ch[1],x);
}
int findkth(node* o,int k)
{
if(k==o->ch[0]->siz+1) return o->x;
else return k<=o->ch[0]->siz?findkth(o->ch[0],k):findkth(o->ch[1],k-(o->ch[0]->siz)-1);
}
int pre(node* o,int x)
{
int k=le(o,x);
return findkth(o,k);
}
int nxt(node* o,int x)
{
int k=leq(o,x);
return findkth(o,k+1);
}
void ins(int x)
{
int k=le(rt,x);
range(k+1,k+1)=newnode(x);
rt->maintain();
}
void rmv(int x)
{
int k=le(rt,x);
range(k+1,k+2)=null;
rt->maintain();
}
int main()
{
init();
scanf("%d",&n);
int op,x;
for(int z=0;z<n;++z){
scanf("%d%d",&op,&x);
if(op==1) ins(x);
else if(op==2) rmv(x);
else if(op==3) printf("%d\n",le(rt,x));
else if(op==4) printf("%d\n",findkth(rt,x+1));
else if(op==5) printf("%d\n",pre(rt,x));
else printf("%d\n",nxt(rt,x));
}
return 0;
}

LinkCutTree

数组version

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
//bzoj 2049
#include <bits/stdc++.h>
using namespace std;
const int maxn=(int)1e4+5;
inline int readInt()
{
char c;int tmp=0,x=1;c=getchar();
while(c>'9' || c<'0') {if(c=='-') x=-1;c=getchar();}
while(c>='0' && c<='9') {tmp=tmp*10+c-'0';c=getchar();}
return tmp*x;
}
int n,m;
struct LinkCutTree{
int f[maxn],ch[maxn][2],siz[maxn],rev[maxn];
void maintain(int o){siz[o]=1+siz[ch[o][0]]+siz[ch[o][1]];}
void pushdown(int o)
{
if(rev[o] && o)
{
if(ch[o][0]) rev[ch[o][0]]^=1;
if(ch[o][1]) rev[ch[o][1]]^=1;
swap(ch[o][0],ch[o][1]);
rev[o]=0;
}
}
bool IsRoot(int o){return ch[f[o]][0]!=o && ch[f[o]][1]!=o;}
int getson(int o){return ch[f[o]][1]==o;}
void rotate(int o)
{
int fa=f[o],ffa=f[fa],d=getson(o);
if(!IsRoot(fa)) ch[ffa][ch[ffa][1]==fa]=o;
ch[fa][d]=ch[o][d^1];f[ch[fa][d]]=fa;
ch[o][d^1]=fa;f[fa]=o;
f[o]=ffa;
maintain(fa),maintain(o);
}
void Allpush(int o)
{
if(!IsRoot(o)) Allpush(f[o]);
pushdown(o);
}
void splay(int o)
{
Allpush(o);
for(int fa=0;!IsRoot(o);rotate(o))
if(!IsRoot(fa=f[o])) rotate(getson(o)==getson(fa)?fa:o);
}
void Access(int o)
{
for(int k=0;o;k=o,o=f[o])
splay(o),ch[o][1]=k;
}
int FindRoot(int o)
{
Access(o),splay(o);
while(ch[o][0]) o=ch[o][0];
return o;
}
void MakeRoot(int o){Access(o),splay(o),rev[o]^=1;}
void Link(int u,int v){MakeRoot(u),f[u]=v,splay(u);}
void Cut(int u,int v){MakeRoot(u),Access(v),splay(v),ch[v][0]=f[u]=0;}
} lct;
char com[21];
int main()
{
n=readInt(),m=readInt();
int x,y;
for(int i=1;i<=m;++i){
scanf("%s",com);
x=readInt(),y=readInt();
if(com[0]=='Q') {
if(lct.FindRoot(x)==lct.FindRoot(y)){
printf("Yes\n");
}else printf("No\n");
}else if(com[0]=='C') {
lct.Link(x,y);
}else if(com[0]=='D') {
lct.Cut(x,y);
}
}
return 0;
}

划分树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
vector<int > dat[maxn<<2];
#define lson (o<<1)
#define rson (o<<1|1)
struct mergetree{
void build(int o,int l,int r)
{
if(l>r) return;
if(l==r) dat[o].push_back(a[l]);
else{
int mid=(l+r)>>1;
build(lson,l,mid),build(rson,mid+1,r);
dat[o].resize(r-l+1);
merge(dat[lson].begin(),dat[lson].end(),dat[rson].begin(),dat[rson].end(),dat[o].begin());
}
}
int Qleq(int o,int l,int r,int ql,int qr,int val)
{
if(ql>r || qr<l) return 0;
if(ql<=l && r<=qr) return upper_bound(dat[o].begin(),dat[o].end(),val)-dat[o].begin();
else{
int mid=(l+r)>>1;
int ret=0;
if(ql<=mid) ret+=Qleq(lson,l,mid,ql,qr,val);
if(qr>mid) ret+=Qleq(rson,mid+1,r,ql,qr,val);
return ret;
}
}
int Qkth(int o,int l,int r,int k)
{
int L=0,R=n;
while(R-L>1){
int mid=(L+R)>>1;
if(Qleq(1,1,n,l,r,mid)>=k) R=mid;
else L=mid;
}
return rfl[R];
}
} Tree;

主席树

不修改

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=100000+5;
int a[maxn],n,m,st[maxn],root[maxn];
namespace sgt {
int sumv[maxn<<5],lson[maxn<<5],rson[maxn<<5],tot=0;
int Newnode(int sum,int Ls,int Rs)
{
sumv[++tot]=sum;
lson[tot]=Ls,rson[tot]=Rs;
return tot;
}
void Ins(int &rt,int prert,int pos,int l,int r)
{
rt=Newnode(sumv[prert]+1,lson[prert],rson[prert]);
if(l==r) return;
int mid=(l+r)>>1;
if(pos<=mid) Ins(lson[rt],lson[prert],pos,l,mid);
else Ins(rson[rt],rson[prert],pos,mid+1,r);
}
int Qry(int S,int E,int l,int r,int k)
{
if(l==r) return l;
int sum=sumv[lson[E]]-sumv[lson[S]],mid=(l+r)>>1;
if(k<=sum) return Qry(lson[S],lson[E],l,mid,k);
else return Qry(rson[S],rson[E],mid+1,r,k-sum);
}
}
using namespace sgt;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]),st[i]=a[i];
sort(st+1,st+1+n);
int sz=unique(st+1,st+1+n)-(st+1);
int pos;
for(int i=1;i<=n;i++) {
pos=lower_bound(st+1,st+1+sz,a[i])-st;
Ins(root[i],root[i-1],pos,1,sz);
}
int l,r,k;
for(int i=1;i<=m;i++) {
scanf("%d%d%d",&l,&r,&k);
printf("%d\n",st[Qry(root[l-1],root[r],1,sz,k)]);
}
return 0;
}

带修改

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <bits/stdc++.h>
using namespace std;
inline int readInt()
{
char c;int tmp=0,x=1;c=getchar();
while(c>'9' || c<'0') {if(c=='-') x=-1;c=getchar();}
while(c>='0' && c<='9') {tmp=tmp*10+c-'0';c=getchar();}
return tmp*x;
}
const int maxn=10000+5;
const int max_log_n=21;
int perfl[max_log_n],perfr[max_log_n],p[2],a[maxn],st[maxn<<1],root[maxn<<1],n,m;
inline int lowbit(int x){return x&(-x);}
namespace sgt {
int tot=0,sumv[maxn<<8],lson[maxn<<8],rson[maxn<<8];
int Newnode(int sum,int Ls,int Rs)
{
sumv[++tot]=sum;
lson[tot]=Ls,rson[tot]=Rs;
return tot;
}
void build(int &rt,int prert,int pos,int l,int r)
{
rt=Newnode(sumv[prert]+1,lson[prert],rson[prert]);
if(l==r) return;
int mid=(l+r)>>1;
if(pos<=mid) build(lson[rt],lson[prert],pos,l,mid);
else build(rson[rt],rson[prert],pos,mid+1,r);
}
void Ins(int &rt,int pos,int l,int r,int val)
{
if(!rt) rt=Newnode(0,0,0);
sumv[rt]+=val;
if(l==r) return;
int mid=(l+r)>>1;
if(pos<=mid) Ins(lson[rt],pos,l,mid,val);
else Ins(rson[rt],pos,mid+1,r,val);
}
int Qry(int l,int r,int k)
{
if(l==r) return l;
int sum=0,mid=(l+r)>>1;
for(int i=0;i<p[0];i++) sum+=sumv[lson[perfr[i]]];
for(int i=0;i<p[1];i++) sum-=sumv[lson[perfl[i]]];
if(k<=sum) {
for(int i=0;i<p[0];i++) perfr[i]=lson[perfr[i]];
for(int i=0;i<p[1];i++) perfl[i]=lson[perfl[i]];
return Qry(l,mid,k);
}else {
for(int i=0;i<p[0];i++) perfr[i]=rson[perfr[i]];
for(int i=0;i<p[1];i++) perfl[i]=rson[perfl[i]];
return Qry(mid+1,r,k-sum);
}
}
};
using namespace sgt;
char com[7];
struct ope {
int a,b,c;
ope(int a=0,int b=0,int c=0): a(a),b(b),c(c) {}
};
ope Q[maxn];
int main()
{
n=readInt(),m=readInt();
for(int i=1;i<=n;i++) a[i]=readInt(),st[i]=a[i];
int l,r,v,up=n;
for(int z=1;z<=m;z++) {
scanf("%s",com);
if(com[0]=='Q') {
l=readInt(),r=readInt(),v=readInt();
Q[z]=ope(l,r,v);
}else {
l=readInt(),v=readInt();
Q[z]=ope(l,v,0);st[++up]=v;
}
}
sort(st+1,st+1+up);
int sz=unique(st+1,st+1+up)-(st+1);
for(int i=1;i<=n;i++) a[i]=lower_bound(st+1,st+1+sz,a[i])-st;
for(int i=1;i<=n;i++) build(root[i+n],root[i-1+n],a[i],1,sz);
for(int z=1;z<=m;z++) {
if(Q[z].c!=0) {
p[0]=p[1]=1;
perfr[0]=root[Q[z].b+n];
perfl[0]=root[Q[z].a-1==0?0:Q[z].a-1+n];
for(int i=Q[z].b;i>0;i-=lowbit(i)) perfr[p[0]++]=root[i];
for(int i=Q[z].a-1;i>0;i-=lowbit(i)) perfl[p[1]++]=root[i];
printf("%d\n",st[Qry(1,sz,Q[z].c)]);
}else {
for(int i=Q[z].a;i<=n;i+=lowbit(i)) Ins(root[i],a[Q[z].a],1,sz,-1);
a[Q[z].a]=lower_bound(st+1,st+1+sz,Q[z].b)-st;
for(int i=Q[z].a;i<=n;i+=lowbit(i)) Ins(root[i],a[Q[z].a],1,sz,1);
}
}
return 0;
}

宗法树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include <bits/stdc++.h>
using namespace std;
const int maxn=(int)1e5+5;
struct Node {
int val,siz;
Node* ch[2];
Node(int val=0,int siz=0): val(val),siz(siz) {ch[0]=ch[1]=NULL;}
bool isleaf() {return ch[0]==NULL;}
void maintain()
{
if(isleaf()) return;
siz=ch[0]->siz+ch[1]->siz;
val=max(ch[0]->val,ch[1]->val);
}
} pool[maxn<<1],*pit,*rt;
void init()
{
pit=pool;
rt=NULL;
}
Node* newNode(int x)
{
pit->val=x; pit->siz=1;
pit->ch[0]=pit->ch[1]=NULL;
return pit++;
}
void rotate(Node* &o,int d)
{
Node* k=o->ch[d^1];
o->ch[d^1]=o->ch[d]; o->ch[d]=o->ch[d^1]->ch[d];
o->ch[d^1]->ch[d]=o->ch[d^1]->ch[d^1]; o->ch[d^1]->ch[d^1]=k;
o->maintain();
}
void Ins(Node* &o,int x)
{
if(o==NULL) { o=newNode(x);return;}
if(o->isleaf()) {
o->ch[0]=newNode(min(x,o->val));
o->ch[1]=newNode(max(x,o->val));
o->maintain();
}else {
if(x>o->ch[0]->val) Ins(o->ch[1],x);
else Ins(o->ch[0],x);
o->maintain();
}
}
void Del(Node* &o,int x,Node* &fa)
{
if(o==NULL) return;
if(o->isleaf()) {
if(o==fa) o=NULL;
else {
if(o==fa->ch[0]) fa=fa->ch[1];
else fa=fa->ch[0];
}
return;
}else {
if(x>o->ch[0]->val) Del(o->ch[1],x,o);
else Del(o->ch[0],x,o);
if(o!=NULL) o->maintain();
}
}
int le(Node* o,int x)
{
if(o==NULL) return 0;
if(o->isleaf()) return o->val<x;
if(x>o->ch[0]->val) return o->ch[0]->siz+le(o->ch[1],x);
else return le(o->ch[0],x);
}
int leq(Node* o,int x)
{
if(o==NULL) return 0;
if(o->isleaf()) return o->val<=x;
if(x>=o->ch[0]->val) return o->ch[0]->siz+leq(o->ch[1],x);
else return leq(o->ch[0],x);
}
int Kth(Node* o,int k)
{
if(o==NULL) assert(0);
if(o->isleaf()) return o->val;
if(k>o->ch[0]->siz) return Kth(o->ch[1],k-o->ch[0]->siz);
else return Kth(o->ch[0],k);
}
void out()
{
Node* ptr;
for(ptr=pool;ptr!=pit;++ptr) {
cout<<ptr<<" : "<<"val= "<<ptr->val<<" siz= "<<ptr->siz<<"\n";
cout<<"ch[0]: ";if(ptr->ch[0]!=NULL) cout<<ptr->ch[0]<<"\n";else cout<<"NULL\n";
cout<<"ch[1]: ";if(ptr->ch[1]!=NULL) cout<<ptr->ch[1]<<"\n";else cout<<"NULL\n";
}puts("");
}
int n;
int main()
{
init();
scanf("%d",&n);
int op,x;
for(int z=0;z<n;z++) {
scanf("%d%d",&op,&x);
if(op==1) Ins(rt,x);
else if(op==2) Del(rt,x,rt);
else if(op==3) printf("%d\n",le(rt,x)+1);
else if(op==4) printf("%d\n",Kth(rt,x));
else if(op==5) printf("%d\n",Kth(rt,le(rt,x)));
else if(op==6) printf("%d\n",Kth(rt,leq(rt,x)+1));
}
return 0;
}

图论

并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int f[maxn],rnk[maxn];
void dsu_init(){for(int i=1;i<=n;i++) f[i]=i,rnk[i]=1;}
int getf(int x){return x==f[x]?f[x]:f[x]=getf(f[x]);}
void merge(int u,int v)
{
int fu=getf(u),fv=getf(v);
if(fu==fv) return;
else{
if(rnk[fu]>rnk[fv]){
rnk[fu]+=rnk[fv];
f[fv]=fu;
}else {
rnk[fv]+=rnk[fu];
f[fu]=fv;
}
}
}

prim

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
using namespace std;
const int maxn=5000+5;
const int inf=0x3f3f3f3f;
vector<pair<int ,int > > g[maxn];
int mincost[maxn],n,m,sel=0;
bool used[maxn];
#define MP make_pair
void prim()
{
int v=-1,ret=0;
memset(mincost,inf,sizeof(mincost));
mincost[1]=0;
while(1)
{
v=-1;
for(int i=1;i<=n;i++){
if(!used[i] && (v==-1 || mincost[v]>mincost[i])) v=i;
}
if(v==-1) break;
sel++;used[v]=true;ret+=mincost[v];
for(int i=0;i<(int)g[v].size();i++){
mincost[g[v][i].second]=min(mincost[g[v][i].second],g[v][i].first);
}
}
if(sel<n-1) printf("orz\n");
else printf("%d\n",ret);
}
int main()
{
scanf("%d%d",&n,&m);
int u,v,w;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&u,&v,&w);
g[u].push_back(MP(w,v));
g[v].push_back(MP(w,u));
}
prim();
return 0;
}

堆优化prim

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;
const int maxn=5000+5,maxm=200000+5;
const int inf=2147483647;
int n,m;
typedef pair<int ,int > pii;
priority_queue<pii,vector<pii>,greater<pii> > pq;
vector<pii> g[maxn];
#define MP make_pair
bool vis[maxn];
int main()
{
scanf("%d%d",&n,&m);
int u,v,w;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&u,&v,&w);
g[u].push_back(MP(w,v));
g[v].push_back(MP(w,u));
}
for(int i=0;i<(int)g[1].size();i++) pq.push(g[1][i]);
vis[1]=true;
int lev=n-1,res=0;
while(lev)
{
pii pv=pq.top();pq.pop();
while(vis[pv.second]) pv=pq.top(),pq.pop();
res+=pv.first;
lev--;
v=pv.second;
vis[v]=true;
for(int i=0;i<(int)g[v].size();i++)
if(!vis[g[v][i].second]) pq.push(g[v][i]);
}
printf("%d\n",res);
return 0;
}

kruscal

1
2
3
4
5
6
7
8
9
10
int lef=n-1;
for(int i=0;i<(int)g.size();i++){
int u=g[i].from,v=g[i].to;
if(getf(u)!=getf(v)) {
addedge(u,v,g[i].cost);
merge(u,v);
lef--;
if(lef==0) break;
}else continue;
}

spfa

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
int dis[maxn];
typedef pair<int ,int > pii;
vector<pii > g[maxn];
void addedge(int from,int to,int cost)
{
g[from].push_back(MP(cost,to));
g[to].push_back(MP(cost,from));
}
bool inque[maxn];
queue<int > Q;
int spfa(int u,int T)
{
memset(dis,inf,sizeof(dis));
dis[u]=0;
Q.push(u);
memset(inque,false,sizeof(inque));
inque[u]=true;
while(!Q.empty())
{
int v=Q.front();Q.pop();inque[v]=false;
for(int i=0;i<(int)g[v].size();i++){
pii e=g[v][i];
if(dis[v]!=inf && dis[e.second]>dis[v]+e.first*del[e.second][v]){
dis[e.second]=dis[v]+e.first*del[e.second][v];
if(!inque[e.second]) {
Q.push(e.second);
inque[e.second]=true;
}
}
}
}
assert(dis[T]!=inf);
return dis[T];
}

循环队列spfa

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <bits/stdc++.h>
using namespace std;
const int maxn=10000+5;
const int maxm=500000+5;
const int inf=2147483647;
int n,m,S;
int tot=0,head[maxn],eg[maxm<<1],nxt[maxm<<1],W[maxm<<1];
void addedge(int u,int v,int w)
{
eg[tot]=v;nxt[tot]=head[u];W[tot]=w;head[u]=tot++;
}
#define MP make_pair
int dis[maxn],q[maxn];
bool inque[maxn];
void spfa()
{
for(int i=1;i<=n;i++) dis[i]=inf;
dis[S]=0;
int hd=0,tl=1;
q[hd]=S;inque[S]=true;
while(hd<=tl)
{
int v=q[hd%n];hd++;
inque[v]=false;
for(int i=head[v];i!=-1;i=nxt[i])
{
int u=eg[i];
if(dis[u]>dis[v]+W[i])
{
dis[u]=dis[v]+W[i];
if(!inque[u]){
inque[u]=true;
q[tl%n]=u;tl++;
}
}
}
}
for(int i=1;i<=n;i++) printf("%d%c",dis[i],i==n?'\n':' ');
}
int main()
{
memset(nxt,-1,sizeof(nxt));
memset(head,-1,sizeof(head));
scanf("%d%d%d",&n,&m,&S);
int u,v,cost;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&u,&v,&cost);
addedge(u,v,cost);
}
spfa();
return 0;
}

dijkstra堆优化

上一个是我写丑了…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
int dis[maxn];
typedef pair<int ,int > pii;
vector<pii > g[maxn];
void addedge(int from,int to,int cost)
{
g[from].push_back(MP(cost,to));
g[to].push_back(MP(cost,from));
}
priority_queue<pii,vector<pii>,greater<pii> > pq;
int dijk(int st,int T)
{
while(!pq.empty()) pq.pop();
memset(dis,inf,sizeof(dis));
dis[st]=0;
pq.push(MP(0,st));
while(!pq.empty()){
int v=pq.top().second,W=pq.top().first;pq.pop();
if(dis[v]<W) continue;
for(int i=0;i<(int)g[v].size();i++){
int u=g[v][i].second,Co=g[v][i].first*del[u][v];
if(dis[v]!=inf && Co+dis[v]<dis[u]){
dis[u]=Co+dis[v];
pq.push(MP(dis[u],u));
}
}
}
assert(dis[T]!=inf);
return dis[T];
}

kosaraju

求强连通分量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
bool vis[maxn];
vector<int > topo;
void dfs1(int v)
{
vis[v]=true;
for(int i=0;i<(int)g[v].size();i++){
int u=g[v][i];
if(!vis[u]) dfs1(u);
}
topo.push_back(v);
}
int sccnum=0,rescc[maxn];
vector<int > scc[maxn];
int ing[maxn],deg[maxn];
void dfs2(int v,int bel)
{
vis[v]=true;scc[bel].push_back(v);rescc[v]=bel;
for(int i=0;i<(int)rg[v].size();i++){
int u=rg[v][i];
if(!vis[u]) dfs2(u,bel);
}
}
void kosaraju()
{
topo.clear();
for(int i=1;i<=n;i++) if(!vis[i]) dfs1(i);
reverse(topo.begin(),topo.end());
memset(vis,0,sizeof(vis[0])*(n+1));
for(int i=0;i<(int)topo.size();i++)
if(!vis[topo[i]]) dfs2(topo[i],++sccnum);
}

树剖

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
int pa[maxn],up[maxn];
ll siz[maxn];
ll dep[maxn];
void dfs(int v,int fa,ll precost)
{
pa[v]=fa;
dep[v]=fa==-1?0:dep[fa]+precost;siz[v]=1;
for(int i=head[v];i!=-1;i=nxt[i]){
int u=ed[i];
if(u!=fa){
dfs(u,v,co[i]);
siz[v]+=siz[u];
}
}
}
int id[maxn],reid[maxn],dfsclock=0;
void dfs2(int v,int fa,int anse)
{
id[v]=++dfsclock;
reid[dfsclock]=v;
up[v]=anse;
int tmpmax=0,tmp=0;
for(int i=head[v];i!=-1;i=nxt[i]){
int u=ed[i];
if(u!=fa && siz[u]>tmp) tmp=siz[u],tmpmax=u;
}
if(tmpmax) dfs2(tmpmax,v,anse);
for(int i=head[v];i!=-1;i=nxt[i]){
int u=ed[i];
if(u==fa || u==tmpmax) continue;
dfs2(u,v,u);
}
}
ll sumv[maxn*10],addv[maxn*10];
#define lson (o<<1)
#define rson ((o<<1)+1)
void maintain(int o,int l,int r)
{
sumv[o]=sumv[lson]+sumv[rson];
sumv[o]+=addv[o]*(r-l+1);
}
void getadd(int o,int l,int r,ll ad)
{
addv[o]+=ad;
maintain(o,l,r);
}
void pushdown(int o,int l,int r)
{
if(addv[o]){
int mid=((l+r)>>1);
getadd(lson,l,mid,addv[o]);
getadd(rson,mid+1,r,addv[o]);
addv[o]=0;
}
maintain(o,l,r);
}
void update(int o,int l,int r,int ql,int qr,ll ad)
{
if(ql>r || qr<l) return;
if(ql<=l && r<=qr) {getadd(o,l,r,ad);return;}
else{
int mid=((l+r)>>1);
pushdown(o,l,r);
if(ql<=mid) update(lson,l,mid,ql,qr,ad);
if(qr>mid) update(rson,mid+1,r,ql,qr,ad);
maintain(o,l,r);
}
}
ll Qnow(int o,int l,int r,int ql,int qr){
if(ql>r || qr<l) return 0ll;
if(ql<=l && r<=qr) {return sumv[o];}
else{
int mid=((l+r)>>1);
pushdown(o,l,r);
ll ret=0;
if(ql<=mid) ret+=Qnow(lson,l,mid,ql,qr);
if(qr>mid) ret+=Qnow(rson,mid+1,r,ql,qr);
maintain(o,l,r);
return ret;
}
}
void getadd(int u,int v)
{
while(up[u]!=up[v]){
update(1,1,n,id[up[u]],id[u],1ll);
u=pa[up[u]];
}
if(u==v) update(1,1,n,id[u],id[u],1ll);
else{
update(1,1,n,id[v],id[u],1ll);
}
}

字符串

manacher

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int kgm[maxn<<1];
ll Manacher(char *s,int n)
{
int mx=-1,pos=-1;
for(int i=0;i<n;i++) {
if(mx>=i) kgm[i]=min(mx-i+1,kgm[pos*2-i]);
else kgm[i]=1;
while(i-kgm[i]>=0 && i+kgm[i]<n && s[i-kgm[i]]==s[i+kgm[i]]) kgm[i]++;
if(i+kgm[i]-1>mx) mx=i+kgm[i]-1,pos=i;
}
ll ret=0;
for(int i=0;i<n;i++) ret=(ret+kgm[i]/2)%mo;
return ret;
}

后缀数组

rnk:下标为$i$对应的$rnk$为多少

sa:下标按后缀大小排序得到的下标序列

在元字符串后面添加一个很小的字符,最小的后缀是它,所以这个最小的经常被忽略不计入答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <bits/stdc++.h>
using namespace std;
#define mem(x) memset(x,0,sizeof(x))
const int maxn=(int)1e5+5;
char _s[maxn];
int len,cnt[maxn],rnk[maxn],rnk1[maxn],rnk2[maxn],tmpsa[maxn],sa[maxn],hei[maxn];
void SuffArr()
{
static char s[maxn]; strcpy(s,_s);
int n=len+1; s[len]=0;
mem(cnt);
for(int i=0;i<n;i++) cnt[(int)s[i]]++;
for(int i=1;i<='z'+1;i++) cnt[i]+=cnt[i-1];
for(int i=0;i<n;i++) rnk[i]=cnt[(int)s[i]]-1;
for(int w=1;w<n;w<<=1) {
for(int i=0;i<n;i++) rnk1[i]=rnk[i],rnk2[i]=i+w<n?rnk[i+w]:0;
mem(cnt);
for(int i=0;i<n;i++) cnt[rnk2[i]]++;
for(int i=1;i<n;i++) cnt[i]+=cnt[i-1];
for(int i=n-1;i>=0;i--) tmpsa[--cnt[rnk2[i]]]=i;
mem(cnt);
for(int i=0;i<n;i++) cnt[rnk1[tmpsa[i]]]++;
for(int i=1;i<n;i++) cnt[i]+=cnt[i-1];
for(int i=n-1;i>=0;i--) sa[--cnt[rnk1[tmpsa[i]]]]=tmpsa[i];
rnk[sa[0]]=0;
bool uni=true;
for(int i=1;i<n;i++) {
rnk[sa[i]]=rnk[sa[i-1]];
if(rnk1[sa[i]]==rnk1[sa[i-1]] && rnk2[sa[i]]==rnk2[sa[i-1]]) uni=false;
else rnk[sa[i]]++;
}
if(uni) break;
}
}
void GetHei()
{
int k=0;
for(int i=0;i<len;i++) {
if(k) k--;
int j=sa[rnk[i]-1];
while(_s[i+k]==_s[j+k]) k++;
hei[rnk[i]]=k;
}
}
int main()
{
scanf("%s",_s);
len=strlen(_s);
SuffArr();
for(int i=1;i<len+1;i++) printf("%d ",sa[i]+1);puts("");
GetHei();
for(int i=2;i<len+1;i++) printf("%d ",hei[i]);puts("");
return 0;
}

优化/数学变换

读入优化/输出优化

1
2
3
4
5
6
7
inline int readint()
{
char c;int tmp=0,x=1;c=getchar();
while(!isdigit(c)){if(c=='-') x=-1;c=getchar();}
while(isdigit(c)){tmp=tmp*10+c-'0';c=getchar();}
return tmp*x;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template<typename T> T readin(T &rd)
{
char c;T tmp=0,x=1;c=getchar();
while(!isdigit(c)){if(c=='-') x=-1;c=getchar();}
while(isdigit(c)){tmp=tmp*10+c-'0';c=getchar();}
return rd=x*tmp;
}
template<typename T> void writeout(T ot)
{
if(ot==0) {putchar('0');return;}
if(ot<0){putchar('-');ot*=-1;}
static char s[21];int idx=0;
while(ot>0) s[++idx]=ot%10+'0',ot/=10;
while(idx) putchar(s[idx--]);
}

随机数

1
2
3
4
int myabs(int x){return x<0?-x:x;}
int rd=1,mo=2147483647,Base=19260817;
int getrand(){rd=((rd*Base+1)&mo);return rd;}
int range(int l,int r){return myabs(getrand())%(r-l+1)+l;}

fft

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
typedef complex<double > cpl;
const double Pi=acos(-1.0);
cpl omg[1<<18],rmg[1<<18];
void fft(cpl *a,int n,cpl *o)
{
int k=0;
while((1<<k)<n) k++;
assert((1<<k)==n);
for(int i=0;i<n;i++) {
int t=0;
for(int j=0;j<k;j++) if((i>>j)&1) t|=(1<<(k-j-1));
if(t>i) swap(a[i],a[t]);
}
cpl t;
for(int l=2;l<=n;l<<=1) {
int hf=l>>1;
for(cpl *x=a;x!=a+n;x+=l)
for(int i=0;i<hf;i++) {
t=o[n/l*i]*x[hf+i];
x[hf+i]=x[i]-t; x[i]+=t;
}
}
}
void dft(cpl *a,int n) {fft(a,n,omg);}
void idft(cpl *a,int n)
{
fft(a,n,rmg);
for(int i=0;i<n;i++) a[i]/=n;
}
void Mul(cpl *a,int n1,cpl *b,int n2)
{
int n=1;
while(n<(n1+n2-1)) n<<=1;
for(int i=0;i<n;i++) omg[i]=cpl(cos(i*2*Pi/n),sin(i*2*Pi/n)),rmg[i]=conj(omg[i]);
dft(a,n), dft(b,n);
for(int i=0;i<n;i++) a[i]*=b[i];
idft(a,n);
}

网络流

费用流

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
//cf739E
#include <bits/stdc++.h>
using namespace std;
const double eps=1e-8;
const int maxn=2000+5;
int n,a,b;
struct edge{
int to;
double cost;int cap,rev;
edge(int to=0,double cost=0,int cap=0,int rev=0): to(to),cost(cost),cap(cap),rev(rev) {}
};
vector<edge> g[maxn];
void addedge(int from,int to,int cap,double cost)
{
cost=-cost;
g[from].push_back(edge(to,cost,cap,g[to].size()));
g[to].push_back(edge(from,-cost,0,g[from].size()-1));
}
double p[maxn],u[maxn];
int S,T,A,B;
#define MP make_pair
bool inque[maxn];
double dis[maxn];
int preve[maxn],prevv[maxn];
queue<int > q;
double spfa()
{
for(int i=S;i<=B;i++) dis[i]=1e60,inque[i]=false;
dis[S]=0;inque[S]=true;
while(!q.empty()) q.pop();
q.push(S);
memset(prevv,0,sizeof(prevv));memset(preve,0,sizeof(preve));
while(!q.empty())
{
int u=q.front();q.pop();inque[u]=false;
for(int i=0;i<(int)g[u].size();i++){
edge &e=g[u][i];
if(e.cap && dis[e.to]-(dis[u]+e.cost)>eps) {
dis[e.to]=dis[u]+e.cost;
preve[e.to]=i,prevv[e.to]=u;
if(!inque[e.to]){
inque[e.to]=true;
q.push(e.to);
}
}
}
}
if(dis[T]>=1e60) return 0;
int gap=INT_MAX;
for(int i=T;i!=S;i=prevv[i]) gap=min(gap,g[prevv[i]][preve[i]].cap);
for(int i=T;i!=S;i=prevv[i]){
edge &e=g[prevv[i]][preve[i]];
e.cap-=gap;
g[i][e.rev].cap+=gap;
}
return dis[T]*(double)gap;
}
double MaxcostMaxflow()
{
double res=0,ret=0;
while((res=spfa())!=0) ret+=res,res=0;
return ret;
}
int main()
{
scanf("%d%d%d",&n,&a,&b);
for(int i=1;i<=n;i++) scanf("%lf",&p[i]);
for(int i=1;i<=n;i++) scanf("%lf",&u[i]);
S=0,T=n+1,A=n+2,B=n+3;
addedge(S,A,a,0),addedge(S,B,b,0);
for(int i=1;i<=n;i++) addedge(A,i,1,p[i]),addedge(B,i,1,u[i]),addedge(i,T,1,0),addedge(i,T,1,-p[i]*u[i]);
printf("%.4lf\n",-MaxcostMaxflow());
return 0;
}

dinic(最大流)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
struct edge{
int to,cap,rev;
edge(int to=0,int cap=0,int rev=0): to(to),cap(cap),rev(rev) {}
};
vector<edge> g[maxn*50];
void addedge(int u,int v,int cap)
{
g[u].push_back(edge(v,cap,(int)g[v].size()));
g[v].push_back(edge(u,0,(int)g[u].size()-1));
}
int n,m,k;
int S,T,ss,tt,N,q[maxn*50+5],dis[maxn*50+5];
bool bfs(int st,int ed)
{
int head=0,tail=0;
memset(dis,-1,sizeof(dis));
dis[st]=0;
q[head]=st;
while(head<=tail) {
int v=q[head%N];head++;
for(int i=0;i<(int)g[v].size();i++) {
edge &e=g[v][i];
if(e.cap>0 && dis[e.to]==-1) {
dis[e.to]=dis[v]+1;
tail++;q[tail%N]=e.to;
}
}
}
return ~dis[ed];
}
int las[maxn*50+5];
int dfs(int v,int ed,int F)
{
if(v==ed) return F;
for(int& i=las[v];i<(int)g[v].size();i++) {
edge &e=g[v][i];
if(e.cap>0 && dis[e.to]==dis[v]+1) {
int d=dfs(e.to,ed,min(F,e.cap));
if(d>0) {
e.cap-=d;
g[e.to][e.rev].cap+=d;
return d;
}
}
}
return 0;
}
int din(int st,int ed)
{
int tmp=0,ret=0;
while(bfs(st,ed)) {
memset(las,0,sizeof(las));
while((tmp=dfs(st,ed,inf))>0) ret+=tmp;
}
return ret;
}

无源汇有上下界可行流

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <bits/stdc++.h>
using namespace std;
const int maxn=200+5;
const int maxm=(int)4e4+5;
const int inf=0x3f3f3f3f;
struct edge{
int id,to,cap,rev;
edge(int id=0,int to=0,int cap=0,int rev=0): id(id),to(to),cap(cap),rev(rev) {}
};
vector<edge> g[maxn];
void addedge(int id,int u,int v,int cap)
{
g[u].push_back(edge(id,v,cap,(int)g[v].size()));
g[v].push_back(edge(0,u,0,(int)g[u].size()-1));
}
int n,m,up[maxm],A[maxn],ans[maxm];
int S,T,N,q[maxn+5],dis[maxn+5];
bool bfs(int st,int ed)
{
int head=0,tail=0;
memset(dis,-1,sizeof(dis));
dis[st]=0;
q[head]=st;
while(head<=tail) {
int v=q[head%N];head++;
for(int i=0;i<(int)g[v].size();i++) {
edge &e=g[v][i];
if(e.cap>0 && dis[e.to]==-1) {
dis[e.to]=dis[v]+1;
tail++;q[tail%N]=e.to;
}
}
}
return ~dis[ed];
}
int las[maxn+5];
int dfs(int v,int ed,int F)
{
if(v==ed) return F;
for(int& i=las[v];i<(int)g[v].size();i++) {
edge &e=g[v][i];
if(e.cap>0 && dis[e.to]==dis[v]+1) {
int d=dfs(e.to,ed,min(F,e.cap));
if(d>0) {
e.cap-=d;
g[e.to][e.rev].cap+=d;
return d;
}
}
}
return 0;
}
int din(int st,int ed)
{
int tmp=0,ret=0;
while(bfs(st,ed)) {
memset(las,0,sizeof(las));
if((tmp=dfs(st,ed,inf))>0) ret+=tmp;
}
return ret;
}
int main()
{
scanf("%d%d",&n,&m);
int u,v,L,R,LOW=0;
for(int i=1;i<=m;i++) {
scanf("%d%d%d%d",&u,&v,&L,&R);
up[i]=R;
addedge(i,u,v,R-L);
A[u]-=L,A[v]+=L;
}
S=0,T=n+1,N=n+5;
for(int i=1;i<=n;i++) {
if(A[i]>0) addedge(0,S,i,A[i]),LOW+=A[i];
else if(A[i]<0) addedge(0,i,T,-A[i]);
}
int fl=din(S,T);
if(fl<LOW) {
printf("NO\n");
exit(0);
}else {
printf("YES\n");
for(int i=1;i<=n;i++) {
for(int j=0;j<(int)g[i].size();j++) {
edge& e=g[i][j];
if(e.id) {
ans[e.id]=up[e.id]-e.cap;
}
}
}
for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
}
return 0;
}

有源汇有上下界最大流

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <bits/stdc++.h>
using namespace std;
const int maxn=205+5;
const int maxm=(int)1e4+5;
const int inf=0x3f3f3f3f;
struct edge{
int id,to,cap,rev;
edge(int id=0,int to=0,int cap=0,int rev=0): id(id),to(to),cap(cap),rev(rev) {}
};
vector<edge> g[maxn];
void addedge(int id,int u,int v,int cap)
{
g[u].push_back(edge(id,v,cap,(int)g[v].size()));
g[v].push_back(edge(0,u,0,(int)g[u].size()-1));
}
int n,m,up[maxm],A[maxn];
int S,T,ss,tt,N,q[maxn+5],dis[maxn+5];
bool bfs(int st,int ed)
{
int head=0,tail=0;
memset(dis,-1,sizeof(dis));
dis[st]=0;
q[head]=st;
while(head<=tail) {
int v=q[head%N];head++;
for(int i=0;i<(int)g[v].size();i++) {
edge &e=g[v][i];
if(e.cap>0 && dis[e.to]==-1) {
dis[e.to]=dis[v]+1;
tail++;q[tail%N]=e.to;
}
}
}
return ~dis[ed];
}
int las[maxn+5];
int dfs(int v,int ed,int F)
{
if(v==ed) return F;
for(int& i=las[v];i<(int)g[v].size();i++) {
edge &e=g[v][i];
if(e.cap>0 && dis[e.to]==dis[v]+1) {
int d=dfs(e.to,ed,min(F,e.cap));
if(d>0) {
e.cap-=d;
g[e.to][e.rev].cap+=d;
return d;
}
}
}
return 0;
}
int din(int st,int ed)
{
int tmp=0,ret=0;
while(bfs(st,ed)) {
memset(las,0,sizeof(las));
if((tmp=dfs(st,ed,inf))>0) ret+=tmp;
}
return ret;
}
int main()
{
scanf("%d%d%d%d",&n,&m,&ss,&tt);
int u,v,L,R,LOW=0;
S=0,T=n+1,N=n+5;
for(int i=1;i<=m;i++) {
scanf("%d%d%d%d",&u,&v,&L,&R);
addedge(i,u,v,R-L);
A[u]-=L;A[v]+=L;
up[i]=R;
}
for(int i=1;i<=n;i++) {
if(A[i]>0) addedge(0,S,i,A[i]),LOW+=A[i];
else addedge(0,i,T,-A[i]);
}
addedge(0,tt,ss,inf);
int fl=din(S,T);
if(fl>=LOW) printf("%d\n",din(ss,tt));
else printf("please go home to sleep\n");
return 0;
}

有源汇有上下界最小流

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
namespace io{
const int L=30000020;
int f;
char ibuf[L],*iS,*iT,c;
inline char Gc(){
if(iS==iT){
iT=(iS=ibuf)+fread(ibuf,1,L,stdin);
return iS==iT?EOF:*iS++;
}
return*iS++;
}
template<class I>void Gi(I&x){
for(f=1,c=Gc();c<'0'||c>'9';c=Gc())if(c=='-')f=-1;
for(x=0;c<='9'&&c>='0';c=Gc())x=x*10+(c&15);x*=f;
}
};
using io::Gi;
namespace mfIO {
inline int readInt()
{
char c;int tmp=0,x=1;c=getchar();
while(c>'9' || c<'0') {if(c=='-') x=-1;c=getchar();}
while(c>='0' && c<='9') {tmp=tmp*10+c-'0';c=getchar();}
return tmp*x;
}
inline ll readLL()
{
char c;ll tmp=0,x=1;c=getchar();
while(c>'9' || c<'0') {if(c=='-') x=-1;c=getchar();}
while(c>='0' && c<='9') {tmp=tmp*10+c-'0';c=getchar();}
return tmp*x;
}
inline void writeInt(int x)
{
if(x==0) {putchar('0');return;}
if(x<0) x*=-1;
char s[21];int tp=0;
while(x>0) s[++tp]=x%10+'0',x/=10;
while(tp) putchar(s[tp--]);
}
inline void writeLL(ll x)
{
if(x==0) {putchar('0');return;}
if(x<0) x*=-1;
char s[21];int tp=0;
while(x>0) s[++tp]=x%10+'0',x/=10;
while(tp) putchar(s[tp--]);
}
}
using mfIO::readInt;
using mfIO::readLL;
using mfIO::writeInt;
using mfIO::writeLL;
const int maxn=50005+5;
const int maxm=125005+5;
const int inf=0x3f3f3f3f;
struct edge{
int id,to,cap,rev;
edge(int id=0,int to=0,int cap=0,int rev=0): id(id),to(to),cap(cap),rev(rev) {}
};
vector<edge> g[maxn];
int tag=-1;
void addedge(int id,int u,int v,int cap,bool lab=false)
{
g[u].push_back(edge(id,v,cap,(int)g[v].size()));
if(lab) tag=(int)g[u].size()-1;
g[v].push_back(edge(0,u,0,(int)g[u].size()-1));
}
int up[maxm],A[maxn];
int dis[maxn],cur[maxn],q[maxn+5],n,m,S,T,N,ss,tt;
bool bfs(int st,int ed)
{
memset(dis,-1,sizeof(dis));
dis[st]=0;
int head=0,tail=0;
q[head]=st;
while(head<=tail) {
int u=q[head%N];head++;
for(int i=0;i<(int)g[u].size();i++) {
edge& e=g[u][i];
if(e.cap>0 && dis[e.to]==-1) {
dis[e.to]=dis[u]+1;
tail++;q[tail%N]=e.to;
}
}
}
return dis[ed]!=-1;
}
int dfs(int v,int ed,int mf)
{
if(v==ed) return mf;
for(int &i=cur[v];i<(int)g[v].size();i++) {
int u=g[v][i].to;
edge& e=g[v][i];
if(e.cap>0 && dis[u]==dis[v]+1) {
int F=dfs(u,ed,min(mf,e.cap));
if(F>0) {
g[v][i].cap-=F;
g[u][g[v][i].rev].cap+=F;
return F;
}
}
}
return 0;
}
int din(int st,int ed)
{
int ret=0,tmp=0;
while(bfs(st,ed)) {
memset(cur,0,sizeof(cur));
while((tmp=dfs(st,ed,inf))>0) ret+=tmp;
}
return ret;
}
int LOW=0;
void AddEdge(int i,int u,int v,int L,int R)
{
addedge(i,u,v,R-L);
A[u]-=L;A[v]+=L;
up[i]=R;
}
void NewEdge(int st,int ed)
{
for(int i=1;i<=n;i++) {
if(A[i]>0) addedge(0,S,i,A[i]),LOW+=A[i];
else addedge(0,i,T,-A[i]);
}
addedge(0,ed,st,inf,1);
}
int pan(int st,int ed)
{
int fl=din(S,T);
if(fl>=LOW) {
int ril=inf-g[ed][tag].cap;
edge & e=g[ed][tag];
e.cap=g[e.to][e.rev].cap=0;
ril-=din(ed,st);
return ril;
}
else return -1;
}
int main()
{
Gi(n),Gi(m),Gi(ss),Gi(tt);
int u,v;
int L,R;
S=0,T=n+1,N=n+5;
for(int i=1;i<=m;i++) {
Gi(u),Gi(v),Gi(L),Gi(R);
AddEdge(i,u,v,L,R);
}
NewEdge(ss,tt);
int ans=pan(ss,tt);
if(ans==-1) puts("please go home to sleep");
else printf("%d\n",ans);
return 0;
}

计算几何

扫描线

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
//poj 2932 accepted
#include <cstdio>
#include <cmath>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=40000+5;
double r[maxn],x[maxn],y[maxn];
int n;
typedef pair<double ,int > pdi;
#define fir first
#define sec second
#define MP make_pair
vector<int > res;
vector<pdi > pts;
set<pdi > out;
typedef set<pdi>::iterator seto;
bool inthe(int i,int j) {return (x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])<=r[j]*r[j];}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%lf%lf%lf",&r[i],&x[i],&y[i]);
}
for(int i=1;i<=n;i++) pts.push_back(MP(x[i]-r[i],i)),pts.push_back(MP(x[i]+r[i],i+n));
sort(pts.begin(),pts.end());
for(int i=0;i<(int)pts.size();i++) {
if(pts[i].sec>n) out.erase(MP(y[pts[i].sec-n],pts[i].sec-n));
else {
seto ite=out.lower_bound(MP(y[pts[i].sec],-1));
if(ite!=out.end() && inthe(pts[i].sec,ite->sec)) continue;
if(ite!=out.begin() && inthe(pts[i].sec,(--ite)->sec)) continue;
out.insert(MP(y[pts[i].sec],pts[i].sec));res.push_back(pts[i].sec);
}
}
sort(res.begin(),res.end());
printf("%d\n",(int)res.size());
for(int i=0;i<(int)res.size();i++) printf("%d%c",res[i],i==(int)res.size()-1?'\n':' ');
return 0;
}