[상단] [Code Library] 25페이지 미만의 자료
템플릿
---
1、NGUNSTTD-PO Name: NeverGiveUpNeverSurrenderTerribleTerribleDamage-PowerOverwhelming
Usage: Put it before main function
Tags: 헤더 파일 순환 일반 문장
---
/** head-file **/
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
#include <algorithm>
/** define-for **/
#define REP(i, n) for (int i=0;i<int(n);++i)
#define FOR(i, a, b) for (int i=int(a);i<int(b);++i)
#define DWN(i, b, a) for (int i=int(b-1);i>=int(a);--i)
#define REP_1(i, n) for (int i=1;i<=int(n);++i)
#define FOR_1(i, a, b) for (int i=int(a);i<=int(b);++i)
#define DWN_1(i, b, a) for (int i=int(b);i>=int(a);--i)
#define REP_N(i, n) for (i=0;i<int(n);++i)
#define FOR_N(i, a, b) for (i=int(a);i<int(b);++i)
#define DWN_N(i, b, a) for (i=int(b-1);i>=int(a);--i)
#define REP_1_N(i, n) for (i=1;i<=int(n);++i)
#define FOR_1_N(i, a, b) for (i=int(a);i<=int(b);++i)
#define DWN_1_N(i, b, a) for (i=int(b);i>=int(a);--i)
/** define-useful **/
#define clr(x,a) memset(x,a,sizeof(x))
#define sz(x) int(x.size())
#define see(x) cerr<<#x<<" "<<x<<endl
#define se(x) cerr<<" "<<x
#define pb push_back
#define mp make_pair
/** test **/
#define Display(A, n, m) { \
REP(i, n){ \
REP(j, m) cout << A[i][j] << " "; \
cout << endl; \
} \
}
#define Display_1(A, n, m) { \
REP_1(i, n){ \
REP_1(j, m) cout << A[i][j] << " "; \
cout << endl; \
} \
}
using namespace std;
/** typedef **/
typedef long long LL;
/** Add - On **/
const int direct4[4][2]={ {0,1},{1,0},{0,-1},{-1,0} };
const int direct8[8][2]={ {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int direct3[6][3]={ {1,0,0},{0,1,0},{0,0,1},{-1,0,0},{0,-1,0},{0,0,-1} };
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const long long INFF = 1LL << 60;
const double EPS = 1e-9;
const double OO = 1e15;
const double PI = acos(-1.0); //M_PI;---------------
2. 도론
---
건도
---
const int maxn=111111;
const int maxm=511111;
int n,m;
struct EDGENODE{
int to;
int w;
int next;
};
struct SGRAPH{
int head[maxn];
EDGENODE edges[maxm];
int edge;
void init()
{
clr(head,-1);
edge=0;
}
void addedge(int u,int v,int c=0)
{
edges[edge].w=c,edges[edge].to=v,edges[edge].next=head[u],head[u]=edge++;
}
}solver;
2 최단거리
---
2.1 최적화된 dijkstra 더미
---
const int maxn=11111;
const int maxm=1111111;
struct EdgeNode{
int to;
int w;
int next;
};
struct HeapNode{
int d,u;
bool operator<(const HeapNode& rhs) const{
return d>rhs.d;
}
};
struct Dijkstra{
EdgeNode edges[maxm];
int head[maxn];
int edge,n;
void init(int n){
this->n=n;
memset(head,-1,sizeof(head));
edge=0;
}
void addedges(int u,int v,int c){
edges[edge].w=c,edges[edge].to=v,edges[edge].next=head[u],head[u]=edge++;
}
bool done[maxn];
int dis[maxn];
int pre[maxn];
void dijkstra(int s){
priority_queue<HeapNode>que;
for (int i=0;i<n;i++) dis[i]=INF;
dis[s]=0;
memset(done,0,sizeof(done));
que.push((HeapNode){0,s});
while (!que.empty()){
HeapNode x=que.top();
que.pop();
int u=x.u;
if (done[u]) continue;
done[u]=true;
for (int i=head[u];i!=-1;i=edges[i].next){
int v=edges[i].to;
int w=edges[i].w;
if (dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
pre[v]=u;
que.push((HeapNode){dis[v],v});
}
}
}
}
}solver;
---
2.2 큐 최적화된 Bellman-Ford
---
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxm=111111;
const int maxn=11111;
struct EdgeNode{
int to;
int w;
int next;
};struct BellmanFord{
EdgeNode edges[maxm];
int head[maxn],edge,n;
bool vis[maxn];
int outque[maxn];
queue<int>que;
int dis[maxn];
void addedge(int u,int v,int c){
edges[edge].w=c,edges[edge].to=v,edges[edge].next=head[u],head[u]=edge++;
}
void init(int n){
memset(head,-1,sizeof(head));
edge=0;
this->n=n;
}
bool spfa(int s){
int u;
for (int i=0;i<=n;i++) dis[i]=INF;
memset(vis,0,sizeof(vis));
memset(outque,0,sizeof(outque));
while (!que.empty()) que.pop();
que.push(s);
vis[s]=true;
dis[s]=0;
while (!que.empty()){
u=que.front();
que.pop();
vis[u]=false;
outque[u]++;
if (outque[u]>n) return false;
for (int i=head[u];i!=-1;i=edges[i].next){
int v=edges[i].to;
int w=edges[i].w;
if (dis[v]==INF||dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
if (!vis[v]){
vis[v]=true;
que.push(v);
}
}
}
}
return true;
}
};---
3연통성
---
3.1 강연통 분량 Tarjan 템플릿
---
const int maxn=111111;
const int maxm=511111;
int n,m;
struct EDGENODE{
int to;
int w;
int next;
};
struct SGRAPH{
int head[maxn];
EDGENODE edges[maxm];
int edge;
void init(int n)
{
clr(head,-1);
edge=0;
}
void addedge(int u,int v,int c=0)
{
edges[edge].w=c,edges[edge].to=v,edges[edge].next=head[u],head[u]=edge++;
}
int pre[maxn],lowlink[maxn],sccno[maxn],scc_cnt,dfs_clock;
stack<int>stk;
void dfs(int u)
{
pre[u]=lowlink[u]=++dfs_clock;
stk.push(u);
for (int i=head[u];i!=-1;i=edges[i].next){
int v=edges[i].to;
if (!pre[v]){
dfs(v);
lowlink[u]=min(lowlink[u],lowlink[v]);
} else if (!sccno[v]){
lowlink[u]=min(lowlink[u],pre[v]);
}
}
if (lowlink[u]==pre[u]){
scc_cnt++;
int x;
do{
x=stk.top();
stk.pop();
sccno[x]=scc_cnt;
}while (x!=u);
}
}
void find_scc(int n)
{
dfs_clock=scc_cnt=0;
clr(sccno,0);
clr(pre,0);
while (!stk.empty()) stk.pop();
REP(i,n) if (!pre[i]) dfs(i);
}
}solver;
3.2 듀얼 연결 템플릿
---
const int maxn=1111;
const int maxm=5111;
int n,m;
struct EDGENODE{
int to;
int w;
bool cut;
int next;
};
struct SEDGE{
int u;
int v;
SEDGE(int uu=0,int vv=0){u=uu;v=vv;}
};
struct BCC_GRAPH{
int head[maxn];
EDGENODE edges[maxm];
int edge;
void init()
{
clr(head,-1);
edge=0;
}
void addedge(int u,int v,int c=0)
{
edges[edge].cut=0,edges[edge].w=c,edges[edge].to=v,edges[edge].next=head[u],head[u]=edge++;
}
//BCC_Tarjan
int dfn[maxn],low[maxn],bccno[maxn],dfs_clock,bcc_cnt;
bool iscut[maxn];
vector<int>bcc[maxn];
stack<SEDGE>stk;
int dfs(int u,int fa)
{
int lowu=dfn[u]=++dfs_clock;
int child=0;
for (int i=head[u];i!=-1;i=edges[i].next)
{
int v=edges[i].to;
if (v==fa) continue;
SEDGE e=SEDGE(u,v);
if (!dfn[v])
{
stk.push(e);
child++;
int lowv=dfs(v,u);
lowu=min(lowu,lowv);
if (dfn[u]<=lowv) //cut
{
iscut[u]=true;
//done
bcc_cnt++;
bcc[bcc_cnt].clear();
SEDGE x;
do{
x=stk.top();
stk.pop();
if (bccno[x.u]!=bcc_cnt)
{
bcc[bcc_cnt].push_back(x.u);
bccno[x.u]=bcc_cnt;
}
if (bccno[x.v]!=bcc_cnt)
{
bcc[bcc_cnt].push_back(x.v);
bccno[x.v]=bcc_cnt;
}
}while (x.u!=u||x.v!=v);
//over
}
if (dfn[u]<lowv) //cut
{
edges[i].cut=true;
edges[i^1].cut=true;
}
}
else if (dfn[v]<dfn[u])
{
stk.push(e);//done
lowu=min(lowu,dfn[v]);
}
}
if (fa<0&&child==1) iscut[u]=0;
low[u]=lowu;
return lowu;
}
void find_bcc(int n)
{
while (!stk.empty()) stk.pop();
clr(dfn,0);
clr(iscut,0);
clr(bccno,0);
dfs_clock=bcc_cnt=0;
REP_1(i,n)
{
if (!dfn[i]) dfs(i,-1);
}
}
//another
int block[maxn];
int vis[maxn];
int b_num;
void b_dfs(int u)
{
vis[u]=true;
block[u]=b_num;
for (int i=head[u];i!=-1;i=edges[i].next)
{
if (edges[i].cut) continue;
int v=edges[i].to;
if (!vis[v]) b_dfs(v);
}
}
void find_block(int n)
{
//find_block
clr(block,0);
clr(vis,0);
b_num=0;
REP_1(i,n)
{
if (!vis[i])
{
b_num++;
b_dfs(i);
}
}
}
}solver;
4 2-SAT
---
4.1 TwoSAT 템플릿
---
const int maxn=2111;
const int maxm=2111111;
int n,m;
struct EDGENODE{
int to;
int next;
};
struct TWO_SAT{
int head[maxn*2];
EDGENODE edges[maxm*2];
int edge;
int n;
bool mark[maxn*2];
int S[maxn*2],c;
void init(int n){
this->n=n;
clr(mark,0);
clr(head,-1);
edge=0;
}
void addedge(int u,int v){
edges[edge].to=v,edges[edge].next=head[u],head[u]=edge++;
}
// x = xval or y = yval
void add_clause(int x,int xval,int y,int yval){
x=x*2+xval;
y=y*2+yval;
addedge(x^1,y);
addedge(y^1,x);
}
void add_con(int x,int xval){
x=x*2+xval;
addedge(x^1,x);
}
bool dfs(int x){
if (mark[x^1]) return false;
if (mark[x]) return true;
mark[x]=true;
S[c++]=x;
for (int i=head[x];i!=-1;i=edges[i].next)
if (!dfs(edges[i].to)) return false;
return true;
}
bool solve(){
for (int i=0;i<n*2;i+=2)
if (!mark[i]&&!mark[i+1]){
c=0;
if (!dfs(i)){
while (c>0) mark[S[--c]]=false;
if (!dfs(i+1)) return false;
}
}
return true;
}
}TwoSAT;
4.2 강연통 Tarjan 고효율 2-SAT
---
const int maxn=11111;
const int maxm=2111111;
int n,m;
struct EDGENODE{
int to;
int next;
};
struct TWO_SAT{
int head[maxn*2];
EDGENODE edges[maxm*2];
int edge;
int n;
void init(int n){
this->n=2*n;
clr(head,-1);
edge=0;
}
void addedge(int u,int v){
edges[edge].to=v,edges[edge].next=head[u],head[u]=edge++;
}
// x = xval or y = yval
void add_clause(int x,int xval,int y,int yval){
x=x*2+xval;
y=y*2+yval;
addedge(x^1,y);
addedge(y^1,x);
}
//x=xval
void add_con(int x,int xval){
x=x*2+xval;
addedge(x^1,x);
}
//
void add_self(int x,int xval,int y,int yval){
x=x*2+xval;
y=y*2+yval;
addedge(x,y);
}
int pre[maxn],lowlink[maxn],sccno[maxn],scc_cnt,dfs_clock;
stack<int>stk;
void dfs(int u)
{
pre[u]=lowlink[u]=++dfs_clock;
stk.push(u);
for (int i=head[u];i!=-1;i=edges[i].next){
int v=edges[i].to;
if (!pre[v]){
dfs(v);
lowlink[u]=min(lowlink[u],lowlink[v]);
} else if (!sccno[v]){
lowlink[u]=min(lowlink[u],pre[v]);
}
}
if (lowlink[u]==pre[u]){
scc_cnt++;
int x;
do{
x=stk.top();
stk.pop();
sccno[x]=scc_cnt;
}while (x!=u);
}
}
void find_scc(int n)
{
dfs_clock=scc_cnt=0;
clr(sccno,0);
clr(pre,0);
while (!stk.empty()) stk.pop();
REP(i,n) if (!pre[i]) dfs(i);
}
bool solve(){
find_scc(n);
for (int i=0;i<n;i+=2){
if (sccno[i]==sccno[i^1]) return false;
}
return true;
}
}TwoSAT;
5 네트워크 흐름
---
5.1 최대 스트리밍 템플릿 Dinic
---
const int INF = 0x3f3f3f3f;
const int maxm=11111;
const int maxn=2222;
struct edgenode{
int to,flow,next;
};
struct Dinic {
int node,src,dest,edge;
int head[maxn],work[maxn],dis[maxn],q[maxn];
edgenode edges[maxm];
void prepare(int _node,int _src,int _dest){
node=_node,src=_src,dest=_dest;
memset(head,-1,sizeof(head));
edge=0;
}
void addedge(int u,int v,int c){
edges[edge].flow=c,edges[edge].to=v,edges[edge].next=head[u],head[u]=edge++;
edges[edge].flow=0,edges[edge].to=u,edges[edge].next=head[v],head[v]=edge++;
}
bool Dinic_bfs() {
int i,u,v,l,r=0;
for (i=0; i<node; i++) dis[i]=-1;
dis[q[r++]=src]=0;
for (l=0; l<r; l++){
for (i=head[u=q[l]]; i!=-1; i=edges[i].next){
if (edges[i].flow&&dis[v=edges[i].to]<0){
dis[q[r++]=v]=dis[u]+1;
if (v==dest) return true;
}
}
}
return false;
}
int Dinic_dfs(int u,int exp){
if (u==dest) return exp;
for (int &i=work[u],v,tmp; i!=-1; i=edges[i].next){
if (edges[i].flow&&dis[v=edges[i].to]==dis[u]+1&&
(tmp=Dinic_dfs(v,min(exp,edges[i].flow)))>0){
edges[i].flow-=tmp;
edges[i^1].flow+=tmp;
return tmp;
}
}
return 0;
}
int Dinic_flow(){
int i,ret=0,delta;
while (Dinic_bfs()){
for (i=0; i<node; i++) work[i]=head[i];
while ( delta=Dinic_dfs(src,INF) ) ret+=delta;
}
return ret;
}
}solver;
---
5.2 최소 비용 최대 흐름
---
const int INF=0x3f3f3f3f;//
const int maxm=1111111;// ，
const int maxn=2222;//
struct edgenode{
int to;//
int flow;//
int cost;//
int next;//
};
struct MinCost{
edgenode edges[maxm];
int node,src,dest,edge;//node ，src ，dest ，edge
int head[maxn],p[maxn],dis[maxn],q[maxn],vis[maxn];//head ，p ，dis
void prepare(int _node=0,int _src=0,int _dest=0){
node=_node,src=_src,dest=_dest;
memset(head,-1,sizeof(head));
memset(vis,0,sizeof(vis));
edge=0;
}
void addedge(int u,int v,int f,int c){
printf("u=%d v=%d f=%d c=%d
",u,v,f,c);
edges[edge].flow=f;edges[edge].cost=c;edges[edge].to=v;
edges[edge].next=head[u];head[u]=edge++;
edges[edge].flow=0;edges[edge].cost=-c;edges[edge].to=u;
edges[edge].next=head[v];head[v]=edge++;
}
bool spfa(){
int i,u,v,l,r=0,tmp;
for (i=0;i<node;i++) dis[i]=INF;
dis[q[r++]=src]=0;
p[src]=p[dest]=-1;
for (l=0;l!=r;((++l>=maxn)?l=0:l)){
for (i=head[u=q[l]],vis[u]=false;i!=-1;i=edges[i].next){
if (edges[i].flow&&dis[v=edges[i].to]>(tmp=dis[u]+edges[i].cost)){
dis[v]=tmp;
p[v]=i^1;
if (vis[v]) continue;
vis[q[r++]=v]=true;
if (r>=maxn) r=0;
}
}
}
return p[dest]>=0;
}
int spfaflow(){
int i,ret=0,delta;
while (spfa()){//
for (i=p[dest],delta=INF;i>=0;i=p[edges[i].to]){
delta=min(delta,edges[i^1].flow);
}
for (int i=p[dest];i>=0;i=p[edges[i].to]){
edges[i].flow+=delta;
edges[i^1].flow-=delta;
}
ret+=delta*dis[dest];
}
return ret;
}
void output(int u){
cout<<u<<endl;
for (int i=head[u];i!=-1;i=edges[i].next){
int v=edges[i].to;
if (edges[i].flow==0&&((i&1)==0)) output(v);
}
}
}solver;---
-------------
6 최소 벡터 없음(New)
-----
struct StoerWagner{
int mat[maxn][maxn];
int dis[maxn];
int S,T;
int n;
bool vis[maxn],del[maxn];
void init(int n){
memset(mat,0,sizeof(mat));
this->n=n;
}
void addedge(int u,int v,int c){
mat[u][v]+=c;
mat[v][u]+=c;
}
int search(int ct){
int tmp,mx,cut;
memset(vis,0,sizeof(vis));
memset(dis,0,sizeof(dis));
T=S=-1;
for (int i=0;i<n-ct;i++){
mx=-1;
for (int j=0;j<n;j++){
if (!vis[j]&&!del[j]&&dis[j]>mx){
mx=dis[j];
tmp=j;
}
}
S=T;
T=tmp;
cut=mx;
vis[T]=true;
for (int j=0;j<n;j++){
if (!vis[j]&&!del[j]){
dis[j]+=mat[T][j];
}
}
}
return cut;
}
int minimumCut(){
int ans=INF;
memset(del,0,sizeof(del));
for (int i=0;i<n-1;i++){
int cut=search(i);
if (cut<ans) ans=cut;
if (ans==0) return 0;
del[T]=true;
for (int j=0;j<n;j++){
if (!del[j]){
mat[S][j]+=mat[T][j];
mat[j][S]+=mat[T][j];
}
}
}
return ans;
}
};
----------------------
LCA 7배 증가
------------------------
void preprocess(){
for (int i=1;i<=n;i++){
anc[i][0]=fa[i];
maxCost[i][0]=cost[i];
for (int j=1;(1<<j)<n;j++) anc[i][j]=-1;
}
for (int j=1;(1<<j)<n;j++){
for (int i=1;i<=n;i++){
if (anc[i][j-1]!=-1){
int a=anc[i][j-1];
anc[i][j]=anc[a][j-1];
maxCost[i][j]=max(maxCost[i][j-1],maxCost[a][j-1]);
}
}
}
}
int query(int p,int q){
int log;
if (L[p]<L[q]) swap(p,q);
for (log=1;(1<<log)<=L[p];log++);log--;
int ans=-INF;
for (int i=log;i>=0;i--){
if (L[p]-(1<<i)>=L[q]){
ans=max(ans,maxCost[p][i]);
p=anc[p][i];
}
}
if (p==q) return ans;
for (int i=log;i>=0;i--){
if (anc[p][i]!=-1&&anc[p][i]!=anc[q][i]){
ans=max(ans,maxCost[p][i]);
p=anc[p][i];
ans=max(ans,maxCost[q][i]);
q=anc[q][i];
}
}
ans=max(ans,cost[p]);
ans=max(ans,cost[q]);
return ans;
} 8 나무
8.1 나무의 중심
class CenterTree{
private:
int sz[maxn];
void dfs(int u,int pa){
sz[u]=1;
for (int i=head[u];i!=-1;i=edges[i].next){
int v=edges[i].to;
if (v==pa) continue;
//if (tree[v].visit) continue;
dfs(v,u);
sz[u]+=sz[v];
}
}
public:
int getCenter(int x){
int p=0;
dfs(x,p);
int cap=sz[x]/2;
bool found=true;
while (found){
found=false;
for (int i=head[x];i!=-1;i=edges[i].next){
int y=edges[i].to;
//if (tree[y].visit) continue;
if (y!=p&&sz[y]>cap){
found=true;
p=x;
x=y;
break;
}
}
}
return x;
}
}coder;8.2 나무의 중심
class TreeCenter{
private:
int f[maxn];
int dp[maxn];
int M,MM;
int dfs(int u,int pa){
int m1=0,m2=0;
for (int i=head[u];i!=-1;i=edges[i].next){
int v=edges[i].to;
if (v==pa) continue;
int t=dfs(v,u);
if (t>m1){
m2=m1;
m1=t;
f[u]=i;
}
else if (t>m2){
m2=t;
}
}
if (M<m1+m2) MM=u,M=m1+m2;
dp[u]=m1;
return dp[u]+1;
}
public:
int getCenter(int n){
M=-1;
dfs(1,-1);
if (M&1){
while (dp[MM]*2>M+1) MM=edges[f[MM]].to;
//int E=f[MM];
addedge(MM,n+1);
addedge(n+1,MM);
addedge(edges[f[MM]].to,n+1);
addedge(n+1,edges[f[MM]].to);
MM=n+1;
}
else{
//int E=0;
while (dp[MM]*2>M) MM=edges[f[MM]].to;
}
return MM;
}
}solver;---------------
3. 데이터 구조
---
1 나무 더미 Treap
---
순위 트리 계발식 합병
#include <iostream>
#include <ctime>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
struct Node{
Node* ch[2];//
int fix;// 。 ，
int key;
int size;//
bool operator<(const Node& rhs) const {
return fix<rhs.fix;
}
int cmp(int x) const{
if (x==key) return -1;
return x<key?0:1;
}
//
void maintain(){
size=1;
if (ch[0]!=NULL) size+=ch[0]->size;
if (ch[1]!=NULL) size+=ch[1]->size;
}
};
struct Treap{
Node* root;
Treap(){
srand(time(0));
root=NULL;
}
void removetree(Node* &t){
if (t->ch[0]!=NULL) removetree(t->ch[0]);
if (t->ch[1]!=NULL) removetree(t->ch[1]);
delete t;
t=NULL;
}
void clear(){
srand(time(0));
removetree(root);
}
Node* newNode(int v){
Node* t=new Node;
t->key=v;
t->ch[0]=t->ch[1]=NULL;
t->fix=rand();
t->size=1;
return t;
}
//d=0 ,d=1
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;
}
// o x, o
void insert(Node* &o,int x){
if (o==NULL) o=newNode(x);
else{
int d=o->cmp(x);
if (d==-1) d=1;
insert(o->ch[d],x);
if (o->ch[d]>o) rotate(o,d^1);
}
o->maintain();
}
void remove(Node* &o,int x){
int d=o->cmp(x);
if (d==-1){
Node* u=o;
if (o->ch[0]!=NULL&&o->ch[1]!=NULL){
int d2=(o->ch[0]>o->ch[1]?1:0);
rotate(o,d2);
remove(o->ch[d2],x);
}else{
if (o->ch[0]==NULL) o=o->ch[1];
else if (o->ch[1]==NULL) o=o->ch[0];
delete u;
}
}
else remove(o->ch[d],x);
if (o!=NULL) o->maintain();
}
bool find(Node* o,int x){
while (o!=NULL){
int d=o->cmp(x);
if (d==-1) return 1;
else o=o->ch[d];
}
return 0;
}
// k
int kth(Node* o,int k){
if (o==NULL||k<=0||k>o->size) return 0;
int s=(o->ch[1]==NULL?0:o->ch[1]->size);
if (k==s+1) return o->key;
else if (k<=s) return kth(o->ch[1],k);
else return kth(o->ch[0],k-s-1);
}
void merge(Node* &src){
if (src->ch[0]!=NULL) merge(src->ch[0]);
if (src->ch[1]!=NULL) merge(src->ch[1]);
insert(root,src->key);
delete src;
src=NULL;
}
};
---
2 스트레칭 트리 Splay
---
2.1 My Splay v1.0
---
/**********************************************************************************
Splay Tree v1.0
Node:
void addIt(int ad) ad
void revIt()
void upd() ,
void pushdown()
Splay:
Node* newNode(int v,Node* f) val v , f,
Node* build(int l,int r,Node* f) [l,r], f;
void rotate(Node* t,int d)
void splay(Node* t,Node* f) t f
void select(int k) k f，
Node*&get(int l, int r) [l,r]， l-1 ，r+1
void reverse(int l,int r) [l,r]
void split(int l,int r,Node*&s1) [l,r] s1
void cut(int l,int r) [l,r]
void init(int n) [1,n]
void show(Node* rt) rt ,debug
void output(int l,int r) [l,r],
:
（ 、 、 ） ，
（ ）Splay 。
，
**********************************************************************************/
#include <iostream>
#include <ctime>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int MAX_N = 150000 + 10;
const int INF = ~0U >> 1;
struct Node{
Node *ch[2],*pre;// ,
int val;//
int size;//
int mx;//
int add;//
bool rev;//
Node(){
size=0;
val=mx=-INF;
add=0;
}
void addIt(int ad){
add+=ad;
mx+=ad;
val+=ad;
}
void revIt(){
rev^=1;
}
void upd(){
size=ch[0]->size+ch[1]->size+1;
mx=max(val,max(ch[0]->mx,ch[1]->mx));
}
void pushdown();
}Tnull,*null=&Tnull;
void Node::pushdown(){
if (add!=0){
for (int i=0;i<2;++i)
if (ch[i]!=null) ch[i]->addIt(add);
add = 0;
}
if (rev){
swap(ch[0],ch[1]);
for (int i=0;i<2;i++)
if (ch[i]!=null) ch[i]->revIt();
rev = 0;
}
}
struct Splay{
Node nodePool[MAX_N],*cur;//
Node* root;//
Splay(){
cur=nodePool;
root=null;
}
// ,init()
void clear(){
cur=nodePool;
root=null;
}
// ,build()
Node* newNode(int v,Node* f){
cur->ch[0]=cur->ch[1]=null;
cur->size=1;
cur->val=v;
cur->mx=v;
cur->add=0;
cur->rev=0;
cur->pre=f;
return cur++;
}
// [l,r] m,init()
Node* build(int l,int r,Node* f){
if(l>r) return null;
int m=(l+r)>>1;
Node* t=newNode(m,f);
t->ch[0]=build(l,m-1,t);
t->ch[1]=build(m+1,r,t);
t->upd();
return t;
}
// ，c=0 ，c=1
void rotate(Node* x,int c){
Node* y=x->pre;
y->pushdown();
x->pushdown();
// y （ y ）
y->ch[!c]=x->ch[c];
if (x->ch[c]!=null) x->ch[c]->pre=y;
x->pre=y->pre;
if (y->pre!=null)
{
if (y->pre->ch[0]==y) y->pre->ch[0]=x;
else y->pre->ch[1]=x;
}
x->ch[c]=y;
y->pre=x;
y->upd();// y
if (y==root) root=x;
}
//Splay ， x f
void splay(Node* x,Node* f){
x->pushdown();// x
while (x->pre!=f){
if (x->pre->pre==f){// f，
if (x->pre->ch[0]==x) rotate(x,1);
else rotate(x,0);
}else{
Node *y=x->pre,*z=y->pre;
if (z->ch[0]==y){
if (y->ch[0]==x) rotate(y,1),rotate(x,1);//
else rotate(x,0),rotate(x,1);//
}else{
if (y->ch[1]==x) rotate(y,0),rotate(x,0);//
else rotate(x,1),rotate(x,0);//
}
}
}
x->upd();// X
}
// k ， f
void select(int k,Node* f){
int tmp;
Node* x=root;
x->pushdown();
k++;//
for(;;){
x->pushdown();
tmp=x->ch[0]->size;
if (k==tmp+1) break;
if (k<=tmp) x=x->ch[0];
else{
k-=tmp+1;
x=x->ch[1];
}
}
splay(x,f);
}
// [l,r]
Node*&get(int l, int r){
select(l-1,null);
select(r+1,root);
return root->ch[1]->ch[0];
}
// [l,r]
void reverse(int l,int r){
Node* o=get(l,r);
o->rev^=1;
splay(o,null);
}
// [l,r] s1
void split(int l,int r,Node*&s1)
{
Node* tmp=get(l,r);
s1=tmp;
root->ch[1]->ch[0]=null;
splay(root->ch[1],null);
}
void cut(int l,int r)
{
Node* tmp;
split(l,r,tmp);
select(root->size-1,null);
select(root->size-2,root);
root->ch[0]->ch[1]=tmp;
tmp->pre=root->ch[0];
splay(tmp,null);
}
//
void init(int n){
clear();
root=newNode(0,null);
root->ch[1]=newNode(n+1,root);
root->ch[1]->ch[0]=build(1,n,root->ch[1]);
splay(root->ch[1]->ch[0],null);
}
// ,debug
void show(Node* rt){
if (rt==null) return;
if (rt->ch[0]!=null) show(rt->ch[0]);
cerr<<"rt="<<rt->val;
if (rt->ch[0]!=null) cerr<<" l="<<rt->ch[0]->val;
if (rt->ch[1]!=null) cerr<<" r="<<rt->ch[1]->val;
if (rt->pre !=null) cerr<<" pre="<<rt->pre->val;
cerr<<endl;
if (rt->ch[1]!=null) show(rt->ch[1]);
}
//
void output(int l,int r){
for (int i=l;i<=r;i++){
select(i,null);
cout<<root->val<<endl;
}
//cout<<endl;
}
}T;
int main()
{
int n,m,a,b;
while (~scanf("%d%d",&n,&m))
{
T.init(n);
while (m--)
{
scanf("%d%d",&a,&b);
if (b<a) swap(a,b);
T.reverse(a,b);
T.cut(a,b);
}
T.output(1,n);
}
return 0;
}2.2 BYVoid's Splay
---
/*
* Problem: NOI2005 sequence
* Author: Guo Jiabao
* Time: 2009.5.30 14:19
* State: Solved
* Memo:
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
const int MAXN=2850003,MAXL=500001,INF=1001;
struct SplayTree
{
struct SplayNode
{
SplayNode *c[2],*f;
int value,size,sum,maxsum,mls,mrs;
bool rev,same;
}*root,*null,*lb,*rb,SS[MAXN];
int SC;
SplayNode * NewNode(int value,SplayNode *f)
{
SplayNode *e=SS+ ++SC;
e->value=value;
e->size=1;e->f=f;
e->sum=e->maxsum=e->mls=e->mrs=value;
e->same=e->rev=false;
e->c[0]=e->c[1]=null;
return e;
}
inline int max(int a,int b){return a>b?a:b;}
void update(SplayNode *p)
{
if (p==null) return;
p->size = p->c[0]->size + p->c[1]->size + 1;
p->sum = p->c[0]->sum + p->c[1]->sum + p->value;
p->mls = p->c[0]->mls;
p->mls = max( p->mls , p->c[0]->sum + p->value);
p->mls = max( p->mls , p->c[0]->sum + p->value + p->c[1]->mls );
p->mrs = p->c[1]->mrs;
p->mrs = max( p->mrs , p->c[1]->sum + p->value);
p->mrs = max( p->mrs , p->c[1]->sum + p->value + p->c[0]->mrs );
p->maxsum = p->value;
p->maxsum = max( p->maxsum , p->c[0]->maxsum );
p->maxsum = max( p->maxsum , p->c[1]->maxsum );
p->maxsum = max( p->maxsum , p->c[0]->mrs + p->value );
p->maxsum = max( p->maxsum , p->c[1]->mls + p->value );
p->maxsum = max( p->maxsum , p->c[0]->mrs + p->c[1]->mls + p->value );
}
void pushdown(SplayNode *p)
{
if (p==null) return;
if (p->rev)
{
p->rev=false;
SplayNode *q=p->c[0]; p->c[0]=p->c[1]; p->c[1]=q;
p->c[0]->rev = !p->c[0]->rev;
p->c[1]->rev = !p->c[1]->rev;
int t=p->mls;
p->mls=p->mrs; p->mrs=t;
}
if (p->same)
{
p->same=false;
p->c[0]->same=p->c[1]->same=true;
p->c[0]->value=p->c[1]->value=p->value;
p->sum = p->maxsum = p->mls = p->mrs = p->value * p->size;
if (p->value < 0)
p->maxsum = p->mls = p->mrs = p->value;
}
}
void rotate(SplayNode *x,int o)//Zig o=0 Zag o=1
{
SplayNode *y=x->f;
pushdown(x->c[0]);
pushdown(x->c[1]);
pushdown(y->c[!o]);
y->c[o] = x->c[!o];
y->c[o]->f=y;
x->f = y->f;
if (y->f->c[0]==y)
y->f->c[0]=x;
else
y->f->c[1]=x;
y->f=x;
x->c[!o]=y;
update(y);
update(x);
if (root==y) root=x;
}
void splay(SplayNode *x,SplayNode *y)
{
pushdown(x);
while (x->f!=y)
{
if (x->f->f==y)
{
if (x->f->c[0]==x)
rotate(x,0);
else
rotate(x,1);
}
else if (x->f->f->c[0] == x->f)
{
if (x->f->c[0]==x)
rotate(x->f,0),rotate(x,0);
else
rotate(x,1),rotate(x,0);
}
else
{
if (x->f->c[1]==x)
rotate(x->f,1),rotate(x,1);
else
rotate(x,0),rotate(x,1);
}
}
}
void select(int k,SplayNode *y)
{
SplayNode *x=root;
pushdown(x);
for (;k != x->c[0]->size + 1;)
{
if (k <= x->c[0]->size)
x=x->c[0];
else
{
k-=x->c[0]->size + 1;
x=x->c[1];
}
pushdown(x);
}
splay(x,y);
}
void Insert(int pos,int tot,int *C)
{
SplayNode *z,*t;
z=t=NewNode(C[1],null);
for (int i=2;i<=tot;i++)
z=z->c[1]=NewNode(C[i],z);
select(pos+1,null);
select(pos+2,root);
root->c[1]->c[0] = t;
t->f=root->c[1];
splay(z,null);
}
void Delete(int pos,int tot)
{
select(pos,null);
select(pos+tot+1,root);
root->c[1]->c[0] = null;
splay(root->c[1],null);
}
void MakeSame(int pos,int tot,int value)
{
select(pos,null);
select(pos+tot+1,root);
root->c[1]->c[0]->same=true;
root->c[1]->c[0]->value=value;
splay(root->c[1]->c[0],null);
}
void Reverse(int pos,int tot)
{
select(pos,null);
select(pos+tot+1,root);
root->c[1]->c[0]->rev=!root->c[1]->c[0]->rev;
splay(root->c[1]->c[0],null);
}
int GetSum(int pos,int tot)
{
select(pos,null);
select(pos+tot+1,root);
pushdown(root->c[1]->c[0]);
return root->c[1]->c[0]->sum;
}
int MaxSum()
{
pushdown(root);
update(root);
return root->maxsum;
}
void init()
{
SC=-1;
null=0;
null=NewNode(-INF,0);
null->size=0;
lb=root=NewNode(-INF,null);
rb=root->c[1]=NewNode(-INF,root);
null->sum = lb->sum = rb->sum=0;
update(root);
}
}Splay;
int N,M,C[MAXL],pos,i,j,A;
char Ctrl[20];
int main()
{
freopen("seq2005.in","r",stdin);
freopen("seq2005.out","w",stdout);
Splay.init();
scanf("%d%d",&N,&M);
for (i=1;i<=N;i++)
scanf("%d",&C[i]);
Splay.Insert(0,N,C);
for (i=1;i<=M;i++)
{
scanf("%s",Ctrl);
switch (Ctrl[0])
{
case 'I':
scanf("%d%d",&pos,&N);
for (j=1;j<=N;j++)
scanf("%d",&C[j]);
Splay.Insert(pos,N,C);
break;
case 'D':
scanf("%d%d",&pos,&N);
Splay.Delete(pos,N);
break;
case 'R':
scanf("%d%d",&pos,&N);
Splay.Reverse(pos,N);
break;
case 'G':
scanf("%d%d",&pos,&N);
A=Splay.GetSum(pos,N);
printf("%d
",A);
break;
case 'M':
if (Ctrl[2]=='K')
{
scanf("%d%d%d",&pos,&N,&C[0]);
Splay.MakeSame(pos,N,C[0]);
}
else
printf("%d
",Splay.MaxSum());
break;
}
}
return 0;
}---
3 트리 배열
---
struct BIT{
int n;
int tree[maxn];
void init(int n){
this->n=n;
memset(tree,0,sizeof(tree));
}
int lowbit(int x){
return x&(-x);
}
void add(int x,int val){
for (int i=x;i<=n;i+=lowbit(i)) tree[i]+=val;
}
int query(int x){
int ret=0;
for (int i=x;i>0;i-=lowbit(i)) ret+=tree[i];
return ret;
}
// p=lower_bound(b+1,b+n+1,a[i])-b;
// x=(i-1)-query(p);add(p,1);
};---
4선 세그먼트 트리
---
4.1 포인트 업데이트
---
const int MAXN=255111;
struct SegmentTree{
int num[MAXN];
struct Tree{
int l;
int r;
int min;
};
Tree tree[MAXN*4];
void push_up(int root){
tree[root].min=min(tree[root<<1].min,tree[root<<1|1].min);
}
void build(int root,int l,int r){
tree[root].l=l;
tree[root].r=r;
if(tree[root].l==tree[root].r){
tree[root].min=num[l];
return;
}
int mid=(l+r)/2;
build(root<<1,l,mid);
build(root<<1|1,mid+1,r);
push_up(root);
}
void update(int root,int pos,int val){
if(tree[root].l==tree[root].r){
tree[root].min=val;
return;
}
int mid=(tree[root].l+tree[root].r)/2;
if(pos<=mid) update(root<<1,pos,val);
else update(root<<1|1,pos,val);
push_up(root);
}
int query(int root,int L,int R){
if(L<=tree[root].l&&R>=tree[root].r) return tree[root].min;
int mid=(tree[root].l+tree[root].r)/2,ret=INF;
if(L<=mid) ret=min(ret,query(root<<1,L,R));
if(R>mid) ret=min(ret,query(root<<1|1,L,R));
return ret;
}
void init(int n,int d){
for (int i=1;i<=n;i++) num[i]=d;
build(1,1,n);
}
};---
4.2 구간 유지 보수
---
const int INF=0x3f3f3f;
const int MAXN=10000;
struct SegTree{
int num[MAXN];
int _min,_max,_sum;
struct Tree{
int l;
int r;
int max;
int min;
int sum;
int add;
int set;
};
Tree tree[MAXN*4];
void push_up(int root){
tree[root].max=max(tree[root<<1].max,tree[root<<1|1].max);
tree[root].min=min(tree[root<<1].min,tree[root<<1|1].min);
tree[root].sum=tree[root<<1].sum+tree[root<<1|1].sum;
}
void push_down(int root){
if (tree[root].set!=-1){
if (tree[root].l!=tree[root].r){
//
tree[root<<1].add=tree[root<<1|1].add=0;
tree[root<<1].set=tree[root<<1|1].set=tree[root].set;
//
tree[root<<1].max=tree[root<<1|1].max=tree[root].set;
//
tree[root<<1].min=tree[root<<1|1].min=tree[root].set;
//
tree[root<<1].sum=(tree[root<<1].r-tree[root<<1].l+1)*tree[root].set;
tree[root<<1|1].sum=(tree[root<<1|1].r-tree[root<<1|1].l+1)*tree[root].set;
}
tree[root].set=-1;
}
if (tree[root].add>0){
if (tree[root].l!=tree[root].r){
//
tree[root<<1].add+=tree[root].add;
tree[root<<1|1].add+=tree[root].add;
//
tree[root<<1].max+=tree[root].add;
tree[root<<1|1].max+=tree[root].add;
//
tree[root<<1].min+=tree[root].add;
tree[root<<1|1].min+=tree[root].add;
//
tree[root<<1].sum+=(tree[root<<1].r-tree[root<<1].l+1)*tree[root].add;
tree[root<<1|1].sum+=(tree[root<<1|1].r-tree[root<<1|1].l+1)*tree[root].add;
}
tree[root].add=0;
}
}
void build(int root,int l,int r){
tree[root].l=l;
tree[root].r=r;
if(tree[root].l==tree[root].r){
tree[root].max=num[l];
tree[root].min=num[l];
tree[root].sum=num[l];
tree[root].add=0;
tree[root].set=-1;
return;
}
int mid=(l+r)/2;
build(root<<1,l,mid);
build(root<<1|1,mid+1,r);
push_up(root);
}
void update_add(int root,int L,int R,int val){
if(L<=tree[root].l&&R>=tree[root].r){
tree[root].add+=val;
tree[root].max+=val;
tree[root].min+=val;
tree[root].sum+=(tree[root].r-tree[root].l+1)*val;
return;
}
push_down(root);
int mid=(tree[root].l+tree[root].r)/2;
if(L<=mid) update_add(root<<1,L,R,val);
if(R>mid) update_add(root<<1|1,L,R,val);
push_up(root);
}
void update_set(int root,int L,int R,int val){
if(L<=tree[root].l&&R>=tree[root].r){
tree[root].set=val;
tree[root].add=0;
tree[root].max=val;
tree[root].min=val;
tree[root].sum=(tree[root].r-tree[root].l+1)*val;
return;
}
push_down(root);
int mid=(tree[root].l+tree[root].r)/2;
if(L<=mid) update_set(root<<1,L,R,val);
if (R>mid) update_set(root<<1|1,L,R,val);
push_up(root);
}
void query(int root,int L,int R){
if(L<=tree[root].l&&R>=tree[root].r){
_min=min(_min,tree[root].min);
_max=max(_max,tree[root].max);
_sum+=tree[root].sum;
return;
}
push_down(root);
int mid=(tree[root].l+tree[root].r)/2;
if(L<=mid) query(root<<1,L,R);
if(R>mid) query(root<<1|1,L,R);
}
};---
---
5 병집
---
int pa[maxn];
void makeset(int n){
for (int i=0;i<=n;i++) pa[i]=i;
}
int findset(int x){
if (x!=pa[x]) pa[x]=findset(pa[x]);
return pa[x];
}
void unionset(int x,int y){
x=findset(x);
y=findset(y);
if (x!=y) pa[x]=y;
}---
6 RMQ
---
6.1 최소값 가져오기
---
int d[maxn][20];
// 1 n
void RMQ_init(int A[],int n){
for (int i=1;i<=n;i++) d[i][0]=A[i];
for (int j=1;(1<<j)<=n;j++)
for (int i=1;i+(1<<j)-1<=n;i++)
d[i][j]=min(d[i][j-1],d[i+(1<<(j-1))][j-1]);
}
int RMQ(int L,int R){
int k=0;
while ((1<<(k+1))<=R-L+1) k++;
return min(d[L][k],d[R-(1<<k)+1][k]);
}---
6.2 최소값의 아래 첨자
---
int d[maxn][20];
// 1 n
void makeRmqIndex(int A[],int n){
for(int i=1;i<=n;i++) d[i][0]=i;
for(int j=1;(1<<j)<=n;j++)
for(int i=1;i+(1<<j)-1<=n;i++)
d[i][j] = A[d[i][j-1]] < A[d[i+(1<<(j-1))][j-1]]? d[i][j-1]:d[i+(1<<(j-1))][j-1];
}
int rmqIndex(int L,int R,int A[])
{
int k=0;
while ((1<<(k+1))<=R-L+1) k++;
return A[d[L][k]]<A[d[R-(1<<k)+1][k]]? d[L][k]:d[R-(1<<k)+1][k];
}---
7 LCA의 RMQ 해법
---
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int INF=0x3f3f3f;
const int maxn=111111;
const int maxm=111111;
int n,m;
struct EDGENODE{
int to;
int w;
int next;
};
struct SGRAPH{
int head[maxn];
EDGENODE edges[maxm];
int edge;
void init(){
memset(head,-1,sizeof(head));
edge=0;
}
void addedge(int u,int v,int c){
edges[edge].w=c,edges[edge].to=v,edges[edge].next=head[u],head[u]=edge++;
}
//------------
int d[maxn][20];
// 1 n
void makeRmqIndex(int A[],int n){
for(int i=1;i<=n;i++) d[i][0]=i;
for(int j=1;(1<<j)<=n;j++)
for(int i=1;i+(1<<j)-1<=n;i++)
d[i][j] = A[d[i][j-1]] < A[d[i+(1<<(j-1))][j-1]]? d[i][j-1]:d[i+(1<<(j-1))][j-1];
}
int rmqIndex(int L,int R,int A[])
{
int k=0;
while ((1<<(k+1))<=R-L+1) k++;
return A[d[L][k]]<A[d[R-(1<<k)+1][k]]? d[L][k]:d[R-(1<<k)+1][k];
}
//---------------------
int E[maxn*2],R[maxn],D[maxn*2],mn;
void dfs(int u,int p,int d){
E[++mn]=u;
D[mn]=d;
R[u]=mn;
for (int i=head[u];i!=-1;i=edges[i].next){
int v=edges[i].to;
if (v==p) continue;
dfs(v,u,d+1);
E[++mn]=u;
D[mn]=d;
}
}
void LCA_init(){
mn=0;
memset(R,0,sizeof(R));
dfs(1,-1,1);
makeRmqIndex(D,mn);
getd(1,-1,0);
}
int LCA(int u,int v){
if (R[u]>=R[v]) return E[rmqIndex(R[v],R[u],D)];
else return E[rmqIndex(R[u],R[v],D)];
}
//--------------------
int deep[maxn];
void getd(int u,int p,int w){
deep[u]=w;
for (int i=head[u];i!=-1;i=edges[i].next){
int v=edges[i].to;
if (v==p) continue;
getd(v,u,w+edges[i].w);
}
}
int getDis(int u,int v){
int lca=LCA(u,v);
return deep[u]+deep[v]-deep[lca]*2;
}
int done(int x,int y,int z){
int ans=INF,res=0;
int lca1,lca2;
lca1=LCA(x,y);
res=deep[x]+deep[y]-deep[lca1]*2;
lca2=LCA(lca1,z);
res+=deep[lca1]+deep[z]-deep[lca2]*2;
ans=min(ans,res);
lca1=LCA(x,z);
res=deep[x]+deep[z]-deep[lca1]*2;
lca2=LCA(lca1,y);
res+=deep[lca1]+deep[y]-deep[lca2]*2;
ans=min(ans,res);
lca1=LCA(y,z);
res=deep[y]+deep[z]-deep[lca1]*2;
lca2=LCA(lca1,x);
res+=deep[lca1]+deep[x]-deep[lca2]*2;
ans=min(ans,res);
return ans;
}
}solver;
---------------
4. 문자열
---
1 사전 트리 Trie
---
const int CHARSET = 26;
const int MAX_N_NODES = int(3e5) + 10;
struct TrieNode
{
TrieNode* next[CHARSET];
int num;//
int value;//
TrieNode(){
memset(next,0,sizeof(next));
value=0;
num=0;
}
void clear(){
memset(next,0,sizeof(next));
value=0;
num=0;
}
}*root;
TrieNode nodePool[MAX_N_NODES],*cur;
TrieNode* newNode(){
TrieNode* t = cur++;
t->clear();
return t;
}
void trieInit() {
cur=nodePool;
root=newNode();
}
// ：
void insert(char* s){
TrieNode* p=root;
int k=0;
while(s[k]!='\0'){
if(!p->next[s[k]-'a']) p->next[s[k]-'a']=newNode();
p=p->next[s[k]-'a'];
p->num++;
k++;
}
p->value=1;
}
//
int find(char* s){
TrieNode* p=root;
int k=0;
while(s[k]!='\0'&&p->next[s[k]-'a']){
p=p->next[s[k]-'a'];
k++;
}
if(s[k]=='\0') return p->num;
return 0;
}
//DP
void dpfind(char* s,int pos){
TrieNode* p=root;
int k=0;
while(s[k]!='\0'&&p->next[s[k]-'a']){
p=p->next[s[k]-'a'];
if (p->value==1){
//do something like dp...
//f[pos+k+1]=(f[pos+k+1]+f[pos])%MOD;
}
k++;
}
}---
f[0]=1; for (int i=1;i<=l;i++) if (f[i-1]) find(str+i,i-1);
---
2 KMP 확장
---
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MM=100005;
int next[MM],extand[MM];
char S[MM],T[MM];
void GetNext(const char *T){
int len=strlen(T),a=0;
next[0]=len;
while(a<len-1 && T[a]==T[a+1]) a++;
next[1]=a;
a=1;
for(int k=2;k<len;k++){
int p=a+next[a]-1,L=next[k-a];
if( (k-1)+L >= p){
int j = (p-k+1)>0 ? (p-k+1) : 0;
while(k+j<len && T[k+j]==T[j]) j++;
next[k]=j;
a=k;
}
else
next[k]=L;
}
}
void GetExtand(const char *S,const char *T){
GetNext(T);
int slen=strlen(S),tlen=strlen(T),a=0;
int MinLen = slen < tlen ? slen : tlen;
while(a<MinLen && S[a]==T[a]) a++;
extand[0]=a;
a=0;
for(int k=1;k<slen;k++){
int p=a+extand[a]-1, L=next[k-a];
if( (k-1)+L >= p){
int j= (p-k+1) > 0 ? (p-k+1) : 0;
while(k+j<slen && j<tlen && S[k+j]==T[j]) j++;
extand[k]=j;
a=k;
}
else
extand[k]=L;
}
}
int main(){
while(scanf("%s%s",S,T)==2){
GetExtand(S,T);
for(int i=0;i<strlen(T);i++)
printf("%d ",next[i]);
puts("");
for(int i=0;i<strlen(S);i++)
printf("%d ",extand[i]);
puts("");
}
return 0;
}
3 Aho-Corasick 로봇
---
const int CHARSET = 26;
const int MAX_N_NODES = int(3e5) + 10;
struct Aho_Corasick{
struct Node{
Node *next[CHARSET];
Node *fail;
int count;//
Node(){
memset(next,0,sizeof(next));
fail = NULL;
count = 0;
}
void clear(){
memset(next,0,sizeof(next));
fail = NULL;
count = 0;
}
};
Node *root;
Node nodePool[MAX_N_NODES], *cur;
Node* newNode(){
Node* t=cur++;
t->clear();
return t;
}
void init(){
cur=nodePool;
root=newNode();
}
void insert(char *str){
Node* p=root;
int i=0,index;
while(str[i]){
index=str[i]-'a';
if(p->next[index]==NULL) p->next[index]=newNode();
p=p->next[index];
i++;
}
p->count++;
}
void build_ac_automation(){
int i;
queue<Node*>Q;
root->fail=NULL;
Q.push(root);
while(!Q.empty()){
Node* temp=Q.front();
Q.pop();
Node* p=NULL;
for(i=0;i<CHARSET;i++){
if(temp->next[i]!=NULL){//
p = temp->fail;
while(p!=NULL){
if(p->next[i]!=NULL){//
temp->next[i]->fail=p->next[i];
break;
}
p=p->fail;
}
if(p==NULL) temp->next[i]->fail=root;// ，
Q.push(temp->next[i]);
}
}
}
}
int query(char *str){// str n
int i=0,cnt=0,index;
Node* p = root;
while(str[i]){
index=str[i]-'a';
while(p->next[index]==NULL&&p!=root) p=p->fail;//
p=p->next[index];
if(p==NULL) p = root;//
Node* temp = p;
while(temp!=root&&temp->count!=-1){//
cnt+=temp->count;
temp->count=-1;
temp=temp->fail;
}
i++;
}
return cnt;
}
};--- ---
4 접미사 배열
---
const int maxn=3e5*2+10;
/******************************************************************
** Suffix Array
** INIT：solver.call_fun(char* s);
** CALL: solver.lcp(int i,int j); // i j
** SP_USE: solver.LCS(char *s1,char* s2); //
******************************************************************/
struct SuffixArray{
int r[maxn];
int sa[maxn],rank[maxn],height[maxn];
int t[maxn],t2[maxn],c[maxn],n;
int m;//
void init(char* s){
n=strlen(s);
for (int i=0;i<n;i++) r[i]=int(s[i]);
m=300;
}
int cmp(int *r,int a,int b,int l){
return r[a]==r[b]&&r[a+l]==r[b+l];
}
/**
r[] ， r[0] r[n-1]， n， m。
r[i] 0,r[n] 0
， sa[] ( 1..n)， sa[1] sa[n]。s[0]
**/
void build_sa(){
int i,k,p,*x=t,*y=t2;
r[n++]=0;
for (i=0;i<m;i++) c[i]=0;
for (i=0;i<n;i++) c[x[i]=r[i]]++;
for (i=1;i<m;i++) c[i]+=c[i-1];
for (i=n-1;i>=0;i--) sa[--c[x[i]]]=i;
for (k=1,p=1;k<n;k*=2,m=p){
for (p=0,i=n-k;i<n;i++) y[p++]=i;
for (i=0;i<n;i++) if (sa[i]>=k) y[p++]=sa[i]-k;
for (i=0;i<m;i++) c[i]=0;
for (i=0;i<n;i++) c[x[y[i]]]++;
for (i=1;i<m;i++) c[i]+=c[i-1];
for (i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];
swap(x,y);
p=1;
x[sa[0]]=0;
for (i=1;i<n;i++) x[sa[i]]=cmp(y,sa[i-1],sa[i],k)?p-1:p++;
}
n--;
}
/**
height[2..n]:height[i] lcp(sa[i],sa[i-1])
rank[0..n-1]:rank[i] suffix[i]
**/
void getHeight(){
int i,j,k=0;
for (i=1;i<=n;i++) rank[sa[i]]=i;
for (i=0;i<n;i++){
if (k) k--;
j=sa[rank[i]-1];
while (r[i+k]==r[j+k]) k++;
height[rank[i]]=k;
}
}
int d[maxn][20];
// 1 n
void RMQ_init(int A[],int n){
for (int i=1;i<=n;i++) d[i][0]=A[i];
for (int j=1;(1<<j)<=n;j++)
for (int i=1;i+j-1<=n;i++)
d[i][j]=min(d[i][j-1],d[i+(1<<(j-1))][j-1]);
}
int RMQ(int L,int R){
int k=0;
while ((1<<(k+1))<=R-L+1) k++;
return min(d[L][k],d[R-(1<<k)+1][k]);
}
void LCP_init(){
RMQ_init(height,n);
}
int lcp(int i,int j){
if (rank[i]>rank[j]) swap(i,j);
return RMQ(rank[i]+1,rank[j]);
}
void call_fun(char* s){
init(s);//
build_sa();// sa
getHeight();// height rank
LCP_init();// RMQ
}
int LCS(char* s1,char* s2){
int p,ans;
int l=strlen(s1);
p=l;
s1[l]='$';
s1[l+1]='\0';
strcat(s1,s2);
call_fun(s1);
ans=0;
for (int i=2;i<=n;i++)
if ((sa[i-1]<p&&sa[i]>p)||(sa[i-1]>p&&sa[i]<p)) ans=max(ans,height[i]);
return ans;
}
}solver;
---
5 문자열 해시
---
H(i)=s[i]+s[i+1]x+...s[n-2]x^(n-2-i)+s[n-1]x^(n-1-i)
Hash(i,L)=s[i]+s[i+1]x+...s[i+L-2]x^(L-2)+s[i+L-1]x^(L-1)
=H[i]-H[i+L]*x^L
LCP(i, j)에 대해서는 L을 2점으로 나눠 해시(i, L)와 해시(j, L)가 같은지 판단한다.
---
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
typedef unsigned long long ULL;
const int SIZE = 100003;
const int SEED = 13331;
const int MAX_N = 50000 + 10;
char s[MAX_N];
struct HASH{
ULL H[MAX_N];
ULL XL[MAX_N];
int len;
HASH(){}
void build(char *s){
len=strlen(s);
H[len]=0;
XL[0]=1;
for (int i=len-1;i>=0;i--){
H[i]=H[i+1]*SEED+s[i];
XL[len-i]=XL[len-i-1]*SEED;
}
}
ULL hash(int i,int L){
return H[i]-H[i+L]*XL[L];
}
}hs;LCP
int lcp(int i,int j){
int l=0,r=min(len-i,len-j);
int res=0;
while (l<=r){
int mid=(l+r)/2;
if (hash(i,mid)==hash(j,mid)){
res=mid;
l=mid+1;
}
else{
r=mid-1;
}
}
return res;
}---
6 접미사 로봇
---
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#define sz(x) int(x.size())
using namespace std;
typedef vector<int> VI;
const int maxn = 250000+10;
class SuffixAutomaton{
private:
struct Node{
Node *suf, *go[26];
int val;
Node(){
suf=NULL;
val=0;
memset(go,0,sizeof(go));
}
void clear(){
suf=NULL;
val=0;
memset(go,0,sizeof(go));
}
int calc(){
if (suf==0) return 0;
return val-suf->val;
}
};
Node *root,*last;
Node nodePool[maxn*2],*cur;
Node* newNode(){
Node* res=cur++;
res->clear();
return res;
}
int tot;
void extend(int w){
Node *p=last;
Node *np=newNode();
np->val=p->val+1;
while (p&&!p->go[w]){
p->go[w]=np;
p=p->suf;
}
if (!p){
np->suf=root;
tot+=np->calc();
}
else{
Node *q=p->go[w];
if (p->val+1==q->val){
np->suf=q;
tot+=np->calc();
}
else{
Node *nq=newNode();
memcpy(nq->go,q->go,sizeof(q->go));
tot-=p->calc()+q->calc();
nq->val=p->val+1;
nq->suf=q->suf;
q->suf=nq;
np->suf=nq;
tot+=p->calc()+q->calc()+np->calc()+nq->calc();
while (p&&p->go[w]==q){
p->go[w]=nq;
p=p->suf;
}
}
}
last = np;
}
public:
void init(){
cur=nodePool;
root=newNode();
last=root;
}
VI getSubString(char s[]){
VI v;
tot=0;
int len=strlen(s);
for (int i=0;i<len;i++){
extend(s[i]-'a');
v.push_back(tot);
}
return v;
}
int getLCS(char A[],char B[]){
int res=0,step=0;
int lenA=strlen(A);
int lenB=strlen(B);
for (int i=0;i<lenA;i++) extend(A[i]-'a');
Node *p=root;
for (int i=0;i<lenB;i++){
int x=B[i]-'a';
if (p->go[x]){
step++;
p=p->go[x];
}
else{
while (p&&!p->go[x]) p=p->suf;
if (!p){
p=root;
step=0;
}
else{
step=p->val+1;
p=p->go[x];
}
}
res=max(res,step);
}
return res;
}
}atm;---------------
기하학
---
1점·선
---
int dcmp(double x){
if (fabs(x)<EPS) return 0;
return x>0?1:-1;
}
struct point{
double x,y;
point(){}
point(double _x,double _y):x(_x),y(_y){}
/** **/
bool operator==(point a)const{
return dcmp(a.x-x)==0&&dcmp(a.y-y)==0;
}
bool operator<(point a)const{
return dcmp(x-a.x)==0?dcmp(y-a.y)<0:dcmp(x-a.x)<0;
}
friend point operator+(point a,point b){
return point(a.x+b.x,a.y+b.y);
}// + =
friend point operator-(point a,point b){
return point(a.x-b.x,a.y-b.y);
}// - =
friend point operator*(point a,double p){
return point(a.x*p,a.y*p);
}// * =
friend point operator/(point a,double p){
return point(a.x/p,a.y/p);
}// / =
/** **/
double len(){
return hypot(x,y);
}
double len2(){
return x*x+y*y;
}
double distance(point p){
return hypot(x-p.x,y-p.y);
}
/** **/
point rotate(double rad){
return point(x*cos(rad)-y*sin(rad),x*sin(rad)+y*cos(rad));
}// rad
point rotate(point p,double angle)// p angle
{
point v=(*this)-p;
double c=cos(angle),s=sin(angle);
return point(p.x+v.x*c-v.y*s,p.y+v.x*s+v.y*c);
}
point rotleft(){
return point(-y,x);
}// 90
point rotright(){
return point(y,-x);
}// 90
point normal(){
double L=len();
return point(-y/L,x/L);
}// 90
point trunc(double r){
double l=len();
if (!dcmp(l)) return *this;
r/=l;
return point(x*r,y*r);
}// r
/** **/
void input(){
scanf("%lf%lf",&x,&y);
}
void output(){
printf("%0.2f %0.2f
",x,y);
}
};
typedef point vect;
double dot(point a,point b){
return a.x*b.x+a.y*b.y;
}
double cross(point a,point b){
return a.x*b.y-a.y*b.x;
}
double area3p(point a,point b,point c){
return cross(b-a,c-a)/2;
}// abc
double angle(vect a,vect b){
return acos(dot(a,b)/a.len()/b.len());
}
point GetLineIntersection(point P,vect v,point Q,vect w){
vect u=P-Q;
double t=cross(w,u)/cross(v,w);
return P+v*t;
}//
double ConvexPolygonArea(point *p,int n){
double area=0;
for (int i=1;i<n-1;i++) area+=cross(p[i]-p[0],p[i+1]-p[0]);
return area/2;
}//
struct line{
point a,b;
line(){}
line(point _a,point _b){a=_a;b=_b;}
line(point p,double angle){
a=p;
if (dcmp(angle-PI/2)==0) b=a+point(0,1);
else b=a+point(1,tan(angle));
}// angle
line (double _a,double _b,double _c){
if (dcmp(_a)==0){
a=point(0,-_c/_b);
b=point(1,-_c/_b);
}else if (dcmp(_b)==0){
a=point(-_c/_a,0);
b=point(-_c/_a,1);
}else{
a=point(0,-_c/_b);
b=point(1,(-_c-_a)/_b);
}
}//ax+by+c=0
void adjust(){
if (b<a) swap(a,b);
}//
/** **/
bool operator==(line v){
return (a==v.a)&&(b==v.b);
}
/** **/
double length(){
return a.distance(b);
}
double angle(){
double k=atan2(b.y-a.y,b.x-a.x);
if (dcmp(k)<0) k+=PI;
if (dcmp(k-PI)==0) k-=PI;
return k;
}
/** **/
int relation(point p){
int c=dcmp(cross(p-a,b-a));
if (c<0) return 1;//
if (c>0) return 2;//
return 3;//
}
bool pointonseg(point p){
return dcmp(cross(p-a,b-a))==0&&dcmp(cross(p-a,p-b))<=0;
}// p ？
bool parallel(line v){
return dcmp(cross(b-a,v.b-v.a))==0;
}// v ？
int segcrossseg(line v){
int d1=dcmp(cross(b-a,v.a-a));
int d2=dcmp(cross(b-a,v.b-a));
int d3=dcmp(cross(v.b-v.a,a-v.a));
int d4=dcmp(cross(v.b-v.a,b-v.a));
if ((d1^d2)==-2&&(d3^d4)==-2)return 2;
return ((d1==0&&dcmp(dot(v.a-a,v.a-b)<=0))||
(d2==0&&dcmp(dot(v.b-a,v.b-b)<=0))||
(d3==0&&dcmp(dot(a-v.a,a-v.b)<=0))||
(d4==0&&dcmp(dot(b-v.a,b-v.b)<=0)));
}// 0- 1- 2-
/** **/
int linecrosseg(line v){// v
int d1=dcmp(cross(b-a,v.a-a));
int d2=dcmp(cross(b-a,v.b-a));
if ((d1^d2)==-2) return 2;
return (d1==0||d2==0);
}//0- 1- 2-
int linecrossline(line v){
if ((*this).parallel(v)) return v.relation(a)==3;
return 2;
}//0- 1- 2-
point crosspoint(line v){
double a1=cross(v.b-v.a,a-v.a);
double a2=cross(v.b-v.a,b-v.a);
return point((a.x*a2-b.x*a1)/(a2-a1),(a.y*a2-b.y*a1)/(a2-a1));
}//
double dispointtoline(point p){
return fabs(cross(p-a,b-a))/length();
}//
double dispointtoseg(point p){
if (dcmp(cross(p-b,a-b))<0||dcmp(cross(p-a,b-a))<0) return min(p.distance(a),p.distance(b));
return dispointtoline(p);
}
/** **/
void input(){
a.input();
b.input();
}
void output(){
a.output();
b.output();
}
};
---------------
수학
---
2수론기초
---
/*==============================================*\
| -
\*==============================================*/
int gcd(int a,int b){
if (b==0) return a;
return gcd(b,a%b);
}
/*==============================================*\
|
| ax+by=gcd(a,b)
\*==============================================*/
int extgcd(int a,int b,int& x,int& y){
int d=a;
if (b!=0){
d=extgcd(b,a%b,y,x);
y-=(a/b)*x;
}else{
x=1;y=0;
}
return d;
}
/*==============================================*\
| -
\*==============================================*/
int prime[maxn];
bool is_prime[maxn+1];
int sieve(int n){
int p=0;
for (int i=0;i<=n;i++) is_prime[i]=true;
is_prime[0]=is_prime[1]=false;
for (int i=2;i<=n;i++){
if (is_prime[i]){
prime[p++]=i;
for (int j=2*i;j<=n;j+=i) is_prime[j]=false;
}
}
return p;
}
/*==============================================*\
|
\*==============================================*/
LL modPow(LL x,LL n,LL mod){
if (n==0) return 1;
LL res=modPow(x*x%mod,n/2,mod);
if (n&1) res=res*x%mod;
return res;
}
/*==============================================*\
| -
| Ax=b,A /
\*==============================================*/
const double eps=1e-8;
typedef vector<double>vec;
typedef vector<vec>mat;
vec gaussJordan(const mat& A,const vec& b){
int n=A.size();
mat B(n,vec(n+1));
for (int i=0;i<n;i++)
for (int j=0;j<n;j++) B[i][j]=A[i][j];
for (int i=0;i<n;i++) B[i][n]=b[i];
for (int i=0;i<n;i++){
int pivot=i;
for (int j=i;j<n;j++){
if (abs(B[j][i])>abs(B[pivot][i])) pivot=j;
}
swap(B[i],B[pivot]);
if (abs(B[i][i]<eps)) return vec();//
for (int j=i+1;j<=n;j++) B[i][j]/=B[i][i];
for (int j=0;j<n;j++){
if (i!=j){
for (int k=i+1;k<=n;k++) B[j][k]-=B[j][i]*B[i][k];
}
}
}
vec x(n);
for (int i=0;i<n;i++) x[i]=B[i][n];
return x;
}
/*==============================================*\
|
| ax≡b(mod m) x=a ×b
| gcd(a,m)!=1
\*==============================================*/
int modInverse(int a,int m){
int x,y;
extgcd(a,m,x,y);
return (m+x%m)%m;
}
2행렬 쾌속멱
---
/*==============================================*\
|
\*==============================================*/
const int M=10000;
typedef vector<int>vec;
typedef vector<vec>mat;
mat mul(mat &A,mat &B){
mat C(A.size(),vec(B[0].size()));
for (int i=0;i<(int)A.size();i++){
for (int k=0;k<(int)B.size();k++){
for (int j=0;j<(int)B[0].size();j++){
C[i][j]=(C[i][j]+A[i][k]*B[k][j])%M;
}
}
}
return C;
}
mat pow(mat A,LL n){
mat B(A.size(),vec(A.size()));
for (int i=0;i<(int)A.size();i++){
B[i][i]=1;
}
while (n>0){
if (n&1) B=mul(B,A);
A=mul(A,A);
n>>=1;
}
return B;
}
---------------
기타
---
1 해시해시
---
1.1 일반hash
#include <iostream>
#include <cstring>
using namespace std;
const int maxn=11111;
const int maxh=10000019;
int head[maxh];
int next[maxh];
long long st[maxn];
void hash_init(){
memset(head,0,sizeof(head));
}
int hash(long long p,int prime=10000019){
int h;
//hash
h=p%prime;
return h;
}
bool add_hash(int s){
int h=hash(st[s]);
int u=head[h];
while(u){
//if (memcmp(st[u],st[s],sizeof(st[s]))==0) return 0;
//if (strcmp(st[u],st[s])==0) return 0;
if (st[u]==st[s]) return 0;
u=next[u];
}
next[s]=head[h];
head[h]=s;
return 1;
}
bool search_hash(long long p){
int h=hash(p);
int u=head[h];
while (u){
//if (memcmp(st[u],p,sizeof(st[u]))==0) return 1;
//if (strcmp(st[u],str)==0) return 1;
if (st[u]==p) return 1;
u=next[u];
}
return 0;
}
---
1.2 나무hash
---
어떤 상수부터 매번 p를 곱하면 하나의 원소와 다르거나 q를 곱하면 나머지를 얻고 p를 곱하면 다음 원소와 다르거나 q를 곱하면 나머지를 얻는다...
마지막 원소까지 진행합니다.마지막으로 얻은 결과를 b에 곱하고 q에 대한 나머지를 취한다.
---
hash[u]=977872;
for(i=0;i<son[u];i++)
{
for(j=i;j<son[u]&&q[i].hash==q[j].hash;j++)
{
hash[u]*=P;
hash[u]^=q[j].hash;
hash[u]%=mod;
}
j--;
ans[u]*=cal(q[i].ans+j-i,j-i+1);
ans[u]%=mod;
i=j;
}---
2 각종 최장자 서열
---
void LXS(int* a,int* f,int n)
{
vector<int>d;
int l,r;
REP(i,n)
{
//l=lower_bound(d.begin(),d.end(),a[i])-d.begin();
r=upper_bound(d.begin(),d.end(),a[i])-d.begin();
if (r==sz(d)) d.push_back(a[i]);
else d[r]=a[i];
f[i]=r+1;
}
}---------------
---------------
---------------
---------------
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
