一些奇怪的模板
#include <cctype>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXSIZE=30000020;
int bufpos;
char buf[MAXSIZE];
void init(){
buf[fread(buf,1,MAXSIZE,stdin)]='\0';
bufpos=0;
}
int readint(){
bool isneg;
int val=0;
for(;!isdigit(buf[bufpos]) && buf[bufpos]!='-';bufpos++);
bufpos+=(isneg=(buf[bufpos]=='-'))?1:0;
for(;isdigit(buf[bufpos]);bufpos++)
val=val*10+buf[bufpos]-'0';
return isneg?-val:val;
}
char readchar(){
for(;isspace(buf[bufpos]);bufpos++);
return buf[bufpos++];
}
struct segtree{
ll minv[maxn*8];
int n,p;
ll v;
segtree(){
memset(minv,0,sizeof(minv));
}
void _update_(int o,int l,int r){
if (l==r){
minv[o]=v;
assert(l==p);
return;
}
ll m=l+(r-l)/2;
//puts("line 35");
if (p<=m)
_update_(o*2,l,m);
else _update_(o*2+1,m+1,r);
minv[o]=min(minv[o*2],minv[o*2+1]);
}
void update(int p,ll v){
this->p=p;
this->v=v;
_update_(1,1,n);
//puts("updated once");
}
int ql,qr;
ll _query_(int o,int l,int r){
if (ql<=l && r<=qr)
return minv[o];
ll ans=INF;
int m=l+(r-l)/2;
if (ql<=m)
ans=min(ans,_query_(o*2,l,m));
if (qr>=m+1)
ans=min(ans,_query_(o*2+1,m+1,r));
return ans;
}
ll query(int l,int r){
if (l>r)
return INF;
ql=l;
qr=r;
return _query_(1,1,n);
}
};
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
struct acatm{
int ch[201][26];
int val[201];
int f[201];
int last[201];
bool match[1000001][21];
int sz,cnt;
acatm(){
sz=1;
cnt=0;
memset(ch[0],0,sizeof(ch[0]));
memset(val,0,sizeof(val));
}
inline int idx(char c){
return c-'a';
}
void ins(char* s){
int len=strlen(s),u=0;
for(int i=0;i<len;i++){
int c=idx(s[i]);
int v=ch[u][c];
if (!v){
ch[u][c]=v=sz++;
memset(ch[v],0,sizeof(ch[v]));
val[v]=0;
}
u=v;
}
val[u]=++cnt;
}
void getfail(){
queue<int> q;
f[0]=0;
last[0]=0;
for(int i=0;i<26;i++){
int u=ch[0][i];
if (u){
q.push(u);
f[u]=0;
last[u]=0;
}
}
while(!q.empty()){
int r=q.front();q.pop();
for(int i=0;i<26;i++){
int u=ch[r][i];
if (!u){
ch[r][i]=ch[f[r]][i];
continue;
}
int v=f[r];
while(v && !ch[v][i])
v=f[v];
f[u]=ch[v][i];
//printf("f[%d]=%d\n",u,f[u]);
last[u]=val[f[u]]?f[u]:last[f[u]];
q.push(u);
}
}
}
void print(int i,int u){
if (u){
match[i][val[u]]=true;
print(i,last[u]);
}
}
void fi(char* s){
memset(match,0,sizeof(match));
int len=strlen(s),u=0;
for(int i=0;i<len;i++){
int c=idx(s[i]);
u=ch[u][c];
//printf("i=%d,u=%d\n",i,u);
if (val[u])
print(i,u);
else if (last[u]) print(i,last[u]);
}
}
};
struct edge{
int from,to,next;
};
struct graph{
int n,m;
edge e[400001];
bool iscut[100001];
bool isbri[400001];
int low[100001];
int pre[100001];
int first[100001];
int cnt;
graph(){
m=0;
cnt=0;
memset(first,-1,sizeof(first));
memset(pre,0,sizeof(pre));
memset(iscut,0,sizeof(iscut));
memset(isbri,0,sizeof(isbri));
}
void addedge(int from,int to){
e[++m]=(edge){from,to,first[from]};
first[from]=m;
}
int dfs(int u,int fa){
int& lowu=low[u];
lowu=pre[u]=++cnt;
int child=0;
for(int i=first[u];i!=-1;i=e[i].next){
int v=e[i].to;
if (!pre[v]){
child++;
int lowv=dfs(v,u);
lowu=min(lowu,lowv);
if (lowv>=pre[u])
iscut[u]=true;
if (lowv>pre[u])
isbri[i]=true; //Only one of (u,v) and (v,u) will be labeled,be careful!
}
else if (pre[v]<pre[u] && v!=fa)
lowu=min(lowu,pre[v]);
}
if (fa<0 && child==1)
iscut[u]=false;
return lowu;
}
};
struct edge{
int from,to,next;
};
struct graph{
int n,m;
edge e[100001];
int first[10001];
int lowlink[10001];
int sccno[10001];
int pre[10001];
int num[10001];
int out0[10001];
int cnt,dfsc;
stack<int> s;
graph(){
m=0;
memset(first,-1,sizeof(first));
}
void addedge(int from,int to){
e[++m]=(edge){from,to,first[from]};
first[from]=m;
}
void dfs(int u){
pre[u]=lowlink[u]=++dfsc;
s.push(u);
for(int i=first[u];i!=-1;i=e[i].next){
int v=e[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]){
cnt++;
for(;;){
int x=s.top();
s.pop();
sccno[x]=cnt;
num[cnt]++;
if (x==u)
break;
}
}
}
void getscc(){
dfsc=cnt=0;
memset(pre,0,sizeof(pre));
memset(sccno,0,sizeof(sccno));
memset(num,0,sizeof(num));
for(int i=1;i<=n;i++)
if (!pre[i])
dfs(i);
}
void rebuild(){
memset(out0,1,sizeof(out0));
for(int i=1;i<=n;i++){
for(int j=first[i];j!=-1;j=e[j].next)
if (sccno[i]!=sccno[e[j].to])
out0[sccno[i]]=false;
}
}
};
#include <cstdio>
#include <cstring>
using namespace std;
struct edge{
int from,to,next;
};
struct twosat{
int n,m;
edge e[2001];
bool mark[201];
int first[201];
int s[201],c;
inline int other(int x){
return x%2?x+1:x-1;
}
twosat(){
m=0;
memset(mark,0,sizeof(mark));
memset(first,-1,sizeof(first));
}
void clear(){
m=0;
memset(mark,0,sizeof(mark));
memset(first,-1,sizeof(first));
}
void addedge(int from,int to){
e[++m]=(edge){from,to,first[from]};
first[from]=m;
}
void addclue(int x,int xval,int y,int yval){
x=x*2+xval-1;
y=y*2+yval-1;
addedge(other(x),y);
addedge(other(y),x);
}
bool dfs(int x){
if (mark[x])
return true;
if (mark[other(x)])
return false;
mark[x]=true;
s[++c]=x;
for(int i=first[x];i!=-1;i=e[i].next){
if (!dfs(e[i].to))
return false;
}
return true;
}
bool solve(){
/*for(int i=1;i<=2*n;i++){
printf("edges from %d:",i);
for(int j=first[i];j!=-1;j=e[j].next)
printf("%d ",e[j].to);
putchar('\n');
}*/
for(int i=1;i<=2*n;i+=2){
if (!mark[i] && !mark[i+1]){
c=0;
if (!dfs(i)){
for(int j=1;j<=c;j++)
mark[s[j]]=false;
c=0;
if (!dfs(i+1))
return false;
}
}
}
return true;
}
};
typedef long long ll;
struct edge{
int from,to;
int dist;
int next;
};
struct graph{
int n,m;
ll d[1002];
edge e[200001];
int first[1002];
bool inq[1002];
int cnt[1002];
int q[2000002];
void init(int n){
this->n=n;
memset(first,-1,sizeof(int)*1002);
m=0;
}
void addedge(int from,int to,int dist){
e[++m]=(edge){from,to,dist,first[from]};
first[from]=m;
}
bool spfa(int s){
//int q[100004];
int f=1,r=1;
memset(d,0x3f,sizeof(ll)*1002);
memset(inq,0,sizeof(int)*1002);
memset(cnt,0,sizeof(int)*1002);
d[s]=0;
q[r]=s;
r++;
inq[s]=true;
cnt[s]=1;
while (f<r){
register int u=q[f];
f++;
inq[u]=false;
register int i=first[u];
while(i!=-1){
register ll t=d[u]+e[i].dist;
register int v=e[i].to;
if(d[u]<INF && d[v]>t){
d[v]=t;
if (!inq[v]){
q[r]=v;
r++;
inq[v]=true;
if (++cnt[v]>n){
return false;
}
}
}
i=e[i].next;
}
}
return true;
}
};
typedef long long ll;
struct edge{
ll from,to,dist,next;
};
struct heapnode{
ll d,u;
bool operator < (const heapnode& rhs) const{
return d>rhs.d;
}
};
struct graph{
ll n,m;
edge* e=new edge[200003];
ll* first=new ll[200003];
ll* d=new ll[200003];
ll* p=new ll[200003];
bool* done=new bool[200003];
void init(ll n){
this->n=n;
m=0;
memset(first,-1,200003*sizeof(ll));
}
void addedge(ll from,ll to,ll dist){
e[++m]=(edge){from,to,dist,first[from]};
first[from]=m;
}
void dijkstra(ll s){
priority_queue<heapnode> q;
memset(d,0x3f,200003*sizeof(ll));
d[s]=0;
memset(done,0,200003*sizeof(bool));
memset(p,0,200003*sizeof(ll));
q.push((heapnode){0,s});
while(!q.empty()){
ll u=q.top().u;
q.pop();
if (done[u])
continue;
done[u]=true;
//prllf("u=%d\n",u);
ll i=first[u];
while (i!=-1){
if (d[u]+e[i].dist<d[e[i].to]){
d[e[i].to]=d[u]+e[i].dist;
p[e[i].to]=u;
q.push((heapnode){d[e[i].to],e[i].to});
}
i=e[i].next;
}
}
}
};
typedef int ll;
int mod;
struct matrix{
int r,c;
ll a[51][51];
matrix(int r,int c){
this->r=r;
this->c=c;
memset(a,0,sizeof(a));
}
ll * operator[](int p){
return a[p];
}
matrix operator =(const matrix& rhs){
//puts("WTF");
assert(r==rhs.r && c==rhs.c);
memcpy(a,rhs.a,sizeof(a));
return *this;
}
matrix operator *(matrix& rhs){
assert(c==rhs.r);
//puts("WTF");
matrix res(r,rhs.c);
//puts("WTF");
for(int i=1;i<=r;i++)
for(int j=1;j<=rhs.c;j++)
for(int k=1;k<=c;k++)
(res[i][j]+=((a[i][k]*rhs[k][j])%mod))%=mod;
//puts("WTF");
return res;
}
matrix operator *=(matrix& rhs){
return *this=(*this)*rhs;
}
};
matrix power(const matrix& mat,ll b){
//puts("WTF");
matrix ret(mat.r,mat.c);
matrix t(mat.r,mat.c);
t=mat;
//puts("line 48");
for(int i=1;i<=mat.r;i++)
ret[i][i]=1;
while(b){
//puts("WTF");
if (b%2)
ret=ret*t;
t=t*t;
b/=2;
}
return ret;
}
struct edge{
int from,to,next;
};
struct graph{
int nl,m;
edge e[maxm];
int first[maxn];
int match[maxn];
bool vis[maxn];
void init(int nl){
this->nl=nl;
m=0;
memset(first,-1,sizeof(first));
}
void addedge(int from,int to){
e[++m]=(edge){from,to,first[from]};
first[from]=m;
}
bool dfs(int u){
for(int i=first[u];i!=-1;i=e[i].next){
int v=e[i].to;
if (!vis[v]){
vis[v]=true;
if (match[v]==-1 || dfs(match[v])){
match[u]=v;
match[v]=u;
return true;
}
}
}
return false;
}
int work(){
int ans=0;
memset(match,-1,sizeof(match));
for(int i=1;i<=nl;i++)
if (match[i]==-1){
memset(vis,0,sizeof(vis));
if (dfs(i))
++ans;
}
return ans;
}
};
struct bit{
int t[32003];
int n;
bit(){
memset(t,0,sizeof(t));
}
inline int lowbit(int x){
return (x&(-x));
}
int sum(int x){
int ret=0;
for(int i=x;i>0;i-=lowbit(i))
ret+=t[i];
return ret;
}
void add(int p,int v){
for(int i=p;i<=n;i+=lowbit(i))
t[i]+=v;
/*for(int i=1;i<=n;i++)
printf("%d ",t[i]);*/
}
};
评论 (0)
