T1
原題：[Codeforces 19E]Fairy。
先不寫題解了，可以參考這裡。
主要就是圖是二分圖的充要條件是沒有基環，然後判斷幾種情況即可。
#include<bits/stdc++.h>
#define N 5000005
using namespace std;
int n,m,t=1;
int dep[N],vis[N],odd[N],even[N],ans[N];
int first[N],v[N<<1],nxt[N<<1];
struct edge{int u,v,odd,even,flag;}e[N];
int in(){
int x=0;char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) x=((x+(x<<2))<<1)+(c^'0'),c=getchar();
return x;
}
void out(int x){
if(x>9) out(x/10);
putchar(x%10+'0');
}
void add(int x,int y){
nxt[++t]=first[x],first[x]=t,v[t]=y;
}
void dfs1(int x){
vis[x]=1;
for(int i=first[x];i;i=nxt[i]){
int to=v[i];
if(vis[to]) continue;
dep[to]=dep[x]+1,e[i/2].flag=1,dfs1(to);
}
}
void dfs2(int x){
vis[x]=1;
for(int i=first[x];i;i=nxt[i]){
int to=v[i];
if(vis[to]) continue;
dfs2(to),even[x]+=even[to],odd[x]+=odd[to];
e[i/2].even=even[to],e[i/2].odd=odd[to];
}
}
int main(){
n=in(),m=in();
for(int i=1;i<=m;++i){
e[i].u=in(),e[i].v=in();
add(e[i].u,e[i].v),add(e[i].v,e[i].u);
}
for(int i=1;i<=n;++i)
if(!vis[i]) dfs1(i);
int cnt=0;
for(int i=1;i<=m;++i){
if(e[i].flag) continue;
int u=e[i].u,v=e[i].v;
if(dep[u]>dep[v]) swap(u,v);
if((dep[v]-dep[u])&1) even[v]++,even[u]--;
else odd[v]++,odd[u]--,cnt++,e[i].odd++;
}
if(!cnt){
out(m),putchar('\n');
for(int i=1;i<=m;++i) out(i),putchar(' ');
return 0;
}
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;++i)
if(!vis[i]) dfs2(i);
int tot=0;
for(int i=1;i<=m;++i){
if(e[i].flag){
if(e[i].odd==cnt&&!e[i].even) ans[++tot]=i;
}
else if(e[i].odd&&cnt==1) ans[++tot]=i;
}
out(tot),putchar('\n');
for(int i=1;i<=tot;++i) out(ans[i]),putchar(' ');
return 0;
}
T2
原題：[BZOJ 3682]Phorni。
法 1 1 1：
我們可以直接用線段樹維護大小關系，在合并區間的時候二分 + + + 哈希判斷大小關系即可。
時間複雜度 O ( n log 2 n ) O(n\log^2n) O(nlog2n)，考試資料比較強隻有 10 10 10 分。
法 2 2 2：
這是字尾平衡樹的模闆題。
相當于是建一顆平衡樹，每個節點代表一個字尾，相當于是在平衡樹上維護字尾的偏序關系。
有關字尾平衡樹我就不都說了，能夠 O ( 1 ) O(1) O(1) 比較的标号法挺強大的。可以看看這篇部落格。
代碼實作就用的替罪羊 + + + 線段樹。
時間複雜度 O ( n log n ) O(n\log n) O(nlogn)。
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5,M=9e5+5;
char S[M],op[5];
int n,m,len,P[N];
namespace Scapegoat{
double L[M],R[M],alpha=0.75;
int root,tot,*bad,lc[M],rc[M],Size[M],order[M];
double val(int x) {return (!x)?-1e18:L[x]+R[x];}
bool comp(int x,int y) {return (S[x]<S[y])||(S[x]==S[y]&&val(x-1)<val(y-1));}
void ins(int &u,int x,double l,double r){
if(!u) {u=x,L[u]=l,R[u]=r,Size[u]=1;return;}
double mid=(l+r)/2;++Size[u];
if(comp(u,x)){
ins(rc[u],x,mid,r);
if(Size[rc[u]]>alpha*Size[u]) bad=&u;
}
else{
ins(lc[u],x,l,mid);
if(Size[lc[u]]>alpha*Size[u]) bad=&u;
}
}
void inorder(int x){
if(lc[x]) inorder(lc[x]);
order[++tot]=x;
if(rc[x]) inorder(rc[x]);
}
int build(int l,int r,double vl,double vr){
if(l>r) return 0;
int mid=(l+r)>>1;double Mid=(vl+vr)/2;
int u=order[mid];L[u]=vl,R[u]=vr,Size[u]=r-l+1;
lc[u]=build(l,mid-1,vl,Mid);
rc[u]=build(mid+1,r,Mid,vr);
return u;
}
void rebuild(int &k){
tot=0,inorder(k);
k=build(1,tot,L[k],R[k]);
}
void Insert(int i){
bad=NULL,ins(root,i,-1e9,1e9);
if(bad!=NULL) rebuild(*bad);
}
}
using namespace Scapegoat;
namespace Segment{
int mn[N<<2];
int Min(int x,int y) {return (P[x]!=P[y]?val(P[x])<val(P[y]):x<y)?x:y;}
#define mid ((l+r)>>1)
void build(int root,int l,int r){
if(l==r) {mn[root]=l;return;}
build(root<<1,l,mid),build(root<<1|1,mid+1,r);
mn[root]=Min(mn[root<<1],mn[root<<1|1]);
}
void Modify(int root,int l,int r,int x){
if(l==r) {mn[root]=x;return;}
if(x<=mid) Modify(root<<1,l,mid,x);
else Modify(root<<1|1,mid+1,r,x);
mn[root]=Min(mn[root<<1],mn[root<<1|1]);
}
int Query(int root,int l,int r,int x,int y){
if(l>=x&&r<=y) return mn[root];
if(y<=mid) return Query(root<<1,l,mid,x,y);
if(x> mid) return Query(root<<1|1,mid+1,r,x,y);
return Min(Query(root<<1,l,mid,x,y),Query(root<<1|1,mid+1,r,x,y));
}
#undef mid
}
using namespace Segment;
int main(){
scanf("%d%d%d%s",&n,&m,&len,S+1);
reverse(S+1,S+len+1);
for(int i=1;i<=len;++i) Insert(i);
for(int i=1;i<=n;++i) scanf("%d",&P[i]);
build(1,1,n);
int x,pos,l,r,last=0;
while(m--){
scanf("%s",op);
if(op[0]=='I') scanf("%d",&x),x^=last,S[++len]=x+'a',Insert(len);
else if(op[0]=='C') scanf("%d%d",&x,&pos),P[x]=pos,Modify(1,1,n,x);
else scanf("%d%d",&l,&r),printf("%d\n",last=Query(1,1,n,l,r));
}
return 0;
}
T3
原題：[Codeforces 768G]The Winds of Winter 。
還沒寫。
大佬部落格。