小tips
CF头
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<cmath>
using namespace std;
template<class T>inline void read(T &x){x=0;char o,f=1;while(o=getchar(),o<48)if(o==45)f=-f;do x=(x<<3)+(x<<1)+(o^48);while(o=getchar(),o>47);x*=f;}
int cansel_sync=(ios::sync_with_stdio(0),cin.tie(0),0);
#define ll long long
#define ull unsigned long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repb(i,a,b) for(int i=(a);i>=b;i--)
#define mkp make_pair
#define ft first
#define sd second
#define log(x) (31-__builtin_clz(x))
#define INF 0x3f3f3f3f
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll gcd(ll a,ll b){ while(b^=a^=b^=a%=b); return a; }
//#define INF 0x7fffffff集合操作
//并交集
vector<int> ANS;
set_union(s1.begin(),s1.end(),s2.begin(),s2.end(),inserter(ANS,ANS.begin()));//set_intersection()
//通过迭代器遍历集合
set<char>::iterator iter = temp1.begin();
while (iter!=temp1.end()){
cout<<*iter;
iter++;
}快读快写
template<class T>inline void read(T &x){x=0;char o,f=1;while(o=getchar(),o<48)if(o==45)f=-f;do x=(x<<3)+(x<<1)+(o^48);while(o=getchar(),o>47);x*=f;}
template<class T>
void wt(T x){//快写
if(x < 0) putchar('-'), x = -x;
if(x >= 10) wt(x / 10);
putchar('0' + x % 10);
}__int128
inline __int128 read(){
__int128 x=0,f=1;
char ch=getchar();
while(ch<‘0‘||ch>‘9‘){
if(ch==‘-‘)
f=-1;
ch=getchar();
}
while(ch>=‘0‘&&ch<=‘9‘){
x=x*10+ch-‘0‘;
ch=getchar();
}
return x*f;
}
inline void print(__int128 x){
if(x<0){
putchar(‘-‘);
x=-x;
}
if(x>9)
print(x/10);
putchar(x%10+‘0‘);
}数据结构
单调队列
普通单调队列
struct node{//结构体，存储数值和位置
int data;
int order;//原本数列里的位置
};
const int MAXN = 1e6+5;
deque<node>dq_min;
deque<node>dq_max;
int n,k;
int a[MAXN];
int res_min[MAXN];
int res_max[MAXN];
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
//如果队列头超过这k的范围，则出队
if(!dq_max.empty()&&dq_max.front().order<i-k+1) dq_max.pop_front();
if(!dq_min.empty()&&dq_min.front().order<i-k+1) dq_min.pop_front();
//新元素从队尾插进来，队尾没用的元素在这里出队
while(!dq_max.empty()&&dq_max.back().data<=a[i]) dq_max.pop_back();
dq_max.push_back(node{a[i],i});
while(!dq_min.empty()&&dq_min.back().data>=a[i]) dq_min.pop_back();
dq_min.push_back(node{a[i],i});
//存储区间最大最小值
res_max[i] = dq_max.front().data;
res_min[i] = dq_min.front().data;
}
for(int i=k;i<=n;i++){
cout<<res_min[i];
if(i!=n) cout<<' ';
}
cout<<endl;
for(int i=k;i<=n;i++){
cout<<res_max[i];
if(i!=n) cout<<' ';
}
cout<<endl;
}
//洛谷 P1886 滑动窗口 /【模板】单调队列 https://www.luogu.com.cn/problem/P1886矩阵上的单调队列
deque<node> dq;//每行进行单调队列
//本来想建maxn个deque的，但是这里发现可以滚动
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(!dq.empty()&&dq.front().order<j-k+1) dq.pop_front();
while(!dq.empty()&&a[i][j]>=dq.back().data) dq.pop_back();
dq.push_back(node{a[i][j],j});
res[i][j] = dq.front().data;
}
dq.clear();
}
//对k开始的每列进行单调队列
for(int j=k;j<=m;j++){
for(int i=1;i<=n;i++){
if(!dq.empty()&&dq.front().order<i-k+1) dq.pop_front();
while(!dq.empty()&&dq.back().data<=res[i][j]) dq.pop_back();
dq.push_back(node{res[i][j],i});
res[i][j] = dq.front().data;
}
dq.clear();
}
ll msum = 0;
for(int i=k;i<=n;i++){
for(int j=k;j<=m;j++){
msum+=res[i][j];
}
}
cout<<msum<<endl;主席树
#define mid ((l+r)>>1)
const int MAXN = 2e5+5;
int n,q,m,cnt=0;
int a[MAXN],b[MAXN];
int T[MAXN];//记录每个时间上树的根节点
int sum[MAXN<<5];//记录节点覆盖区间内数字的数量
int L[MAXN<<5],R[MAXN<<5];//记录左右儿子
int build(int l,int r){//一开始通过递归建树
int pos = ++cnt;//建立新的节点，节点数cnt自增
sum[pos]=0;//时间0时是没有任何数字的
if(l<r){
L[pos]=build(l,mid);
R[pos]=build(mid+1,r);
}
return pos;
}
int update(int pre,int l,int r,int x){//pre是在pos位置上一个时间的节点编号
int pos = ++cnt;
L[pos]=L[pre];R[pos]=R[pre];//pre是上个时间点在如今pos位置上的节点
//这里相当于是把这个新的节点接到相应的位置
sum[pos] = sum[pre]+1;//这一整条链上各点的权值都+1(叶子上加了1，上面的都受影响)
if(l<r){//找到长度为一个数的节点就结束递归了
if(x<=mid) L[pos] = update(L[pre],l,mid,x);
else R[pos] = update(R[pre],mid+1,r,x);
//判断数值x的这个节点在当前节点的左儿子还是右儿子
//这样一直沿着这条链往下，建立新的节点。
//因为pos节点的儿子中新建立的节点需要返回编号
}
return pos;
}
int query(int u,int v,int l,int r,int k){
if(l>=r) return l;
int x = sum[L[v]]-sum[L[u]];//计算左子树中数的数量x
if(x>=k) return query(L[u],L[v],l,mid,k);//x比k大，说明第k大的数在左子树中
else return query(R[u],R[v],mid+1,r,k-x);
}
int main(){
cin>>n>>q;
rep(i,1,n){
cin>>a[i];
b[i]=a[i];
}
sort(b+1,b+1+n);
m = unique(b+1,b+1+n)-b-1;//排序后可以用unique函数去重
T[0] = build(1,m);
rep(i,1,n){
int t = lower_bound(b+1,b+1+m,a[i]) - b;//找到对应的离散化后的数值
T[i] = update(T[i-1],1,m,t);//建立新时间的根节点，并且建新的链并接上去
}
while(q--){
int u,v,k;
cin>>u>>v>>k;//找u到v区间内第k大的数
int t = query(T[u-1],T[v],1,m,k);
cout<<b[t]<<endl;//输出对应的原值
}
}
//洛谷P3834 【模板】可持久化线段树 2（主席树）
//https://www.luogu.com.cn/problem/P3834
//其实就是拿的大爹板子然后自己加了很多注释：
//https://www.luogu.com.cn/blog/bestFy0731/solution-p3834LCA
#define log(x) (31-__builtin_clz(x))//谢谢hjt
constexpr int LOGN = log(MAXN)/log(2)+5;
int z,m,n;
int fa[MAXN],p[MAXN][LOGN];
int L[MAXN];//记录深度
int lg[MAXN];
vector<int> e[MAXN];
void init_lg(){//预处理lg，给之后计算省时间
lg[1]=0;
for(int i=2;i<MAXN;i++) lg[i]=lg[i-1]+( (1<<(lg[i-1]+1))==i );
}
void dfs(int x){
for(auto u:e[x]){
L[u]=L[x]+1;
dfs(u);
}
}
void preprocess(int n){
for(int i=1;i<=n;i++)
for(int j=0;1<<j<=n;j++) p[i][j]=-1;//有些倍增后出界的，用-1标记
for(int i=1;i<=n;i++)
p[i][0]=fa[i];//倍增长度为1的时候指向格子的父节点
for(int j=1;1<<j<=n;j++)
for(int i=1;i<=n;i++)
if(p[i][j-1]!=-1) p[i][j]=p[p[i][j-1]][j-1];//两端长度加起来正好是两倍即次数+1
}
int LCA(int u,int v){
if(L[u]<L[v]) swap(u,v);//u成为离根节点更远的
int log = lg[L[u]];//找到L[u]的二进制最高位
for(int i=log;i>=0;i--)
if(L[u]-(1<<i)>=L[v]) u=p[u][i];//u往上爬到与v同高
if(u==v) return u;
for(int i=log;i>=0;i--)
if(p[u][i]!=-1&&p[u][i]!=p[v][i]){//找公共祖先,逼近它但是又不超过它
u=p[u][i]; v=p[v][i];
}
return fa[u];
}
int main(){
init_lg();//预处理log2x，给之后的计算省时间
int z,q,u,v;
string aa,bb;
cin>>z;
while(z--){
map<string,int>mp;
cin>>n>>q;
if(n==1){
while(q--){
cin>>aa>>bb;cout<<0<<endl;
}
continue;
}
int countt = 0;
for(int i=1;i<=n;i++){
fa[i]=i;
}
for(int i=1;i<n;i++){
cin>>aa>>bb;
int &a = mp[aa];int &b = mp[bb];
if(!a) a=++countt;
if(!b) b=++countt;
fa[a]=b;
e[b].push_back(a);
}
int rt;
for(int i=1;i<=n;i++){
if(fa[i]==i) {
rt=i;break;
}
}
L[rt]=1;
dfs(rt);
preprocess(n);
int res;
while(q--){
cin>>aa>>bb;
int &a = mp[aa];int &b = mp[bb];
int lc = LCA(a,b);
res = L[a]-L[lc];
if(lc!=b) res++;
cout<<res<<endl;
}
for(int i=1;i<=n;i++) e[i].clear();
}
}
//HDOJ4547 http://acm.hdu.edu.cn/showproblem.php?pid=4547树链剖分
ll ans;
int da[MAXN];//记录dfn序上的各点数值用来初始化线段树
int n,m,rt,p;//节点数，询问数，根，模数
struct tree{
int sum;
int lazy;
};
struct St{//线段树
tree t[MAXN<<2];
void pushup(int pos){
t[pos].sum=(t[pos<<1].sum+t[pos<<1|1].sum) %p;
return;
}
void pushdown(int l,int r,int pos){
if(!t[pos].lazy) return;
int mid = (l+r)>>1;
t[pos<<1].sum += t[pos].lazy*(mid-l+1);
t[pos<<1].sum %= p;//取模
t[pos<<1|1].sum += t[pos].lazy*(r-(mid+1)+1);
t[pos<<1|1].sum %= p;//取模
t[pos<<1].lazy += t[pos].lazy;
t[pos<<1].lazy %= p;//取模
t[pos<<1|1].lazy += t[pos].lazy;
t[pos<<1|1].lazy %= p;//取模
t[pos].lazy = 0;
}
void build(int l,int r,int pos){
t[pos].sum = t[pos].lazy = 0;
if(l==r){
t[pos].sum = da[l];
return;
}
int mid = (l+r)>>1;
build(l,mid,pos<<1);
build(mid+1,r,pos<<1|1);
pushup(pos);
}
void update(int L,int R,int l,int r,int pos,int v){
if(L<=l&&r<=R){
t[pos].sum += v*(r-l+1);
t[pos].lazy += v;
t[pos].lazy %= p;//取模
return;
}
if(r<L||l>R) return;
pushdown(l,r,pos);
int mid = (l+r)>>1;
update(L,R,l,mid,pos<<1,v);
update(L,R,mid+1,r,pos<<1|1,v);
pushup(pos);
}
void query(int L,int R,int l,int r,int pos){
if(L<=l&&r<=R){
ans += t[pos].sum;
ans%=p;//取模
return;
}
if(r<L||R<l) return;
pushdown(l,r,pos);
int mid = (l+r)>>1;
query(L,R,l,mid,pos<<1);
query(L,R,mid+1,r,pos<<1|1);
return;
}
//查询和修改，为了简化参数，我又写了两个
ll tquery(int L,int R){
ans = 0;
query(L,R,1,n,1);
return ans;
}
void tupdate(int L,int R,int v){
update(L,R,1,n,1,v);
}
};
//树结构
vector<int> e[MAXN];//记录边
int a[MAXN];//记录编号对应节点的初始数值
//树剖部分
St segt;
int si[MAXN],dep[MAXN],fa[MAXN],rem[MAXN],dfn[MAXN],top[MAXN];
int dfn_num;
void dfs1(int x,int faa){//预处理出fa,dep,si,rem
int ma = 0;//用来x的重儿子，记录最大的size
si[x] = 1;
for(auto v:e[x]){
if(v==faa) continue;//跳过父亲节点
dep[v] = dep[x]+1;//更新儿子的dep
dfs1(v,x);
si[x] += si[v];//x的size加上当前儿子的size
fa[v] = x;//标记v的父节点为x
if(si[v]>ma){
ma = si[v];
rem[x] = v;//记录重儿子
}
}
}
void dfs2(int x,int faa){//预处理出dfn，top
if(rem[faa]==x) top[x] = top[faa];//同一条重链同一个top
else top[x] = x;//否则为重链头
dfn[x] = ++dfn_num;//更新树剖序，同时下标自增
da[dfn_num] = a[x];
if(rem[x]) dfs2(rem[x],x);//优先遍历重儿子
for(auto v:e[x]){
if(v==faa) continue;
if(v==rem[x]) continue;//重儿子之前已经遍历过了
dfs2(v,x);
}
}
inline ll cal(int L,int R){
return segt.tquery(L,R);
}
void init(){//初始化
dfn_num=0;
dfs1(rt,0);
dfs2(rt,0);
segt.build(1,n,1);//这里通过da来初始化线段树
}
ll query(int x,int y){
ll res=0;
while(top[x]!=top[y]){//跳到同一条重链
if(dep[top[x]]<dep[top[y]])swap(x,y);
//重链深度更大的点优先往上跳
res += cal(dfn[top[x]],dfn[x]);//算上这条重链的
res%=p;//取模
x = fa[top[x]];//跳到重链头的父节点上
}
//跳出这个循环时，xy已经在同一个重链上了
res += cal(min(dfn[x],dfn[y]),max(dfn[x],dfn[y]));
res%=p;//取模
//xy不确定顺序对不对，所以取minmax
return res;
}
void update(int x,int y,int v){
ll res=0;
while(top[x]!=top[y]){//跳到同一条重链
if(dep[top[x]]<dep[top[y]])swap(x,y);
//重链深度更大的点优先往上跳
segt.tupdate(dfn[top[x]],dfn[x],v);//更新数值
x = fa[top[x]];//跳到重链头的父节点上
}
//跳出这个循环时，xy已经在同一个重链上了
segt.tupdate(min(dfn[x],dfn[y]),max(dfn[x],dfn[y]),v);
//xy不确定顺序对不对，所以取minmax
}
int main(){
cin>>n>>m>>rt>>p;//节点数，操作数，根节点序号，模数
for(int i=1;i<=n;i++){
cin>>a[i];//记录初始数值
a[i] = a[i]%p;
}
int x,y;
for(int i=1;i<=n;i++) e[i].clear();
for(int i=1;i<n;i++){
cin>>x>>y;
e[x].push_back(y);
e[y].push_back(x);
}
init();
int v;
int typ;
while(m--){
cin>>typ;
if(typ==1){//简单路径上修改
cin>>x>>y>>v;
update(x,y,v);
}
else if(typ==2){//简单路径上查询
cin>>x>>y;
cout<<query(x,y)<<endl;
}
else if(typ==3){//子树上修改
cin>>x>>v;
segt.tupdate(dfn[x],dfn[x]+si[x]-1,v);
}
else if(typ==4){//子树上查询
cin>>x;
cout<<segt.tquery(dfn[x],dfn[x]+si[x]-1)<<endl;
}
}
}
//洛谷 P3384 【模板】轻重链剖分 https://www.luogu.com.cn/problem/P3384splay
int root,tot,n;
struct Node{
int ch[2];//左右儿子
int val;//值
int fa;//父节点
int size;//子树大小
int cnt;//计数
}t[MAXN];
inline void pushup(int x){//维护节点的size
t[x].size = t[x].cnt;//自己重复的次数先累计
if(t[x].ch[0]) t[x].size+=t[t[x].ch[0]].size;
if(t[x].ch[1]) t[x].size+=t[t[x].ch[1]].size;
//如果有儿子,把儿子的size加到自己
//同线段树的pushup必须先处理儿子再处理父节点
}
void rotate(int x){//旋转操作
int y=t[x].fa, z=t[y].fa;
int k=(t[y].ch[1]==x);//x是y的左还是右儿子
t[z].ch[t[z].ch[1]==y] = x;//x换到y原来在的位置
t[x].fa = z;
t[y].ch[k] = t[x].ch[k^1];//y顶下来x的儿子，放在x原来对y的位置
t[t[x].ch[k^1]].fa = y;
t[x].ch[k^1] = y;//y换到 x原来在y的 相对的 位置
t[y].fa = x;
pushup(y),pushup(x);//更新size,因为y是儿子,所以先y
}//这里的异或是用来调整0和1(左右儿子)
inline void splay(int x,int goal){//找到x并把x旋转为goal的儿子根节点
while(t[x].fa!=goal){//x一直旋转到成为goal的儿子
int y=t[x].fa,z=t[y].fa;
if(z!=goal)//如果y不是根节点,分两类讨论
(t[z].ch[0]==x)^(t[y].ch[0]==y)?rotate(x):rotate(y);
//x和y分别是y和z的同一侧儿子,先转y再转x;不同则先转x转两次
rotate(x);//无论三种情况中的哪一种都要最后转x
}
if(goal==0) root=x;//若goal是0,根节点更新为x
}
inline void find(int x){//查找x的位置,并旋转x到根节点,类似二分,O(logn)
int u = root;
if(!u) return;//树是空的情况
while(t[u].ch[x>t[u].val]&&x!=t[u].val)//找到x,不一定找得到
u = t[u].ch[x>t[u].val];//左儿子小，右儿子大
splay(u,0);//当前位置旋转到根节点.根节点的fa存0
}
inline void insert(int x){//类似find,如果插入的数已经存在,可以在找到的节点计数
int u = root,fu = 0;//当前位置u,u的爸爸fu
while(u&&t[u].val!=x){//找合适位置,u找到空的地方也会停止
fu = u;
u = t[u].ch[x>t[u].val];
}
if(u) t[u].cnt++;//已有这个数字的情况,计数
else{
u = ++tot;//节点总数tot+1
if(fu)//这时候fu是上一个u即新插入u的父节点,如果父节点不是0
t[fu].ch[x>t[fu].val]=u;
t[u].ch[0] = t[u].ch[1] = 0;//这个新节点没儿子
t[u].fa = fu;//父亲
t[u].val = x;//数值
t[u].cnt = 1;//计数
t[u].size = 1;//大小
}
splay(u,0);
}
inline int Next(int x,int f){
find(x);
int u=root;//根节点，此时x的父节点(存在的话)就是根节点
//这里sls回答了我的疑问
//"splay中不一定有x这个节点,那么它splay到根的就直接可以满足了"
//"如果有这个点的话就要在splay上再找一波(因为当前的根就是x这个点)"
if(t[u].val>x&&f)return u;//如果当前节点的值大于x并且要查找的是后继
if(t[u].val<x&&!f)return u;//如果当前节点的值小于x并且要查找的是前驱
//上面两个是x不在splay中的情况
u = t[u].ch[f];//后继在根右边找,前驱在左边找
while(t[u].ch[f^1]) u = t[u].ch[f^1];//左半边要往右跳找最大的,右半边往左跳
return u;
}
inline void Delete(int x){//删除x
int last = Next(x,0);//查找x的前驱
int next = Next(x,1);//找x的后继
splay(last,0);splay(next,last);//前驱节点转到根节点,后继转到根的儿子上
//操作完之后.后继是前驱的右儿子,x是前驱的左儿子,而且x是叶子节点
int del = t[next].ch[0];//后继的左儿子x
if(t[del].cnt>1){
t[del].cnt--;//如果有多个x,则x的计数减少一个
splay(del,0);//这个splay还重新pushup计算了del的子树
}
else
t[next].ch[0]=0;//因为是左儿子是叶子节点,直接丢掉
}
inline int kth(int x){//找第k小,改一下也可以找第k大
int u=root;
return 0;
while(1){
int y = t[u].ch[0];//左儿子
if(x>t[y].size+t[u].cnt){//如果左儿子和当前点的size比要找的排名数小
x-=t[y].size+t[u].cnt;//数量减少,相当于把这个寻找排名的起点变成了当前节点
u=t[u].ch[1];//那么当前排名的数一定要往右儿子上找
}
else if(t[y].size>=x) u=y;//左儿子的size足够,儿子在左侧上找
else return t[u].val;//左儿子的size比x小,加上当前点u的size则比x大,说明第kA大的就是x
}
}
int main(){
tot=0;
read(n);
insert(+2147483647);insert(-2147483647);//博客作者在这里先加了正负INF
int typ,x;
while(n--){
read(typ);
if(typ==1){read(x);insert(x);}//插入
else if(typ==2){read(x);Delete(x);}//删除
else if(typ==3){//查找
read(x);find(x);
printf("%d\n",t[t[root].ch[0]].size);
}
else if(typ==4){//第k小
read(x);printf("%d\n",kth(x+1));//之前插进去正负INF,所以要+1;
}
else if(typ==5){//前驱
read(x);printf("%d\n",t[Next(x,0)].val);
}
else if(typ==6){//后继
read(x);printf("%d\n",t[Next(x,1)].val);
}
}
return 0;
}
//基本是抄的这个大爹的博客https://www.cnblogs.com/cjyyb/p/7499020.html
//再自己加了一点注解
//全部代码https://paste.ubuntu.com/p/gH5mWpz669/多项式
FFT
递归FFT
inline int read(){
char c=getchar();int x=0,f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
const int MAXN = 3e6+5;
const double Pi = acos(-1.0);
struct cplx{//手写负数complex用起来会更快
double x,y;
cplx(double x=0,double y=0):x(x),y(y){}
friend cplx operator + (cplx a,cplx b){return cplx(a.x+b.x,a.y+b.y);}
friend cplx operator - (cplx a,cplx b){return cplx(a.x-b.x,a.y-b.y);}
friend cplx operator * (cplx a,cplx b){return cplx(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}
}a[MAXN],b[MAXN];
void FFT(int limit,cplx *a,int type){//limit记录项数
if(limit==1) return;//只有一个常数项结束递归(即只剩下0次的)
cplx a1[limit>>1],a2[limit>>1];//按照奇偶分组
for(int i=0;i<limit;i+=2)
a1[i>>1] = a[i],a2[i>>1] = a[i+1];
FFT(limit>>1,a1,type);
FFT(limit>>1,a2,type);
cplx Wn(cos(2*Pi/limit),type*sin(2*Pi/limit));//单位根
//这里type挺重要的,反变换的时候用-1,因为是-k
cplx w(1,0);//一会儿算单位根幂的时候用w存
cplx tmp;
for(int i=0;i<(limit>>1);i++,w=w*Wn){//w相当于公式中的w_n^k
tmp = w*a2[i];//蝴蝶操作
a[i]=a1[i]+tmp;//偶
a[i+(limit>>1)]=a1[i]-tmp;//O(1)算另外一部分
}
}
int main(){
int n=read(),m=read();
rep(i,0,n) a[i].x=read();
rep(i,0,m) b[i].x=read();
int limit = 1;
while(limit<=n+m) limit<<=1;//这里非常精髓
//把长度补到2的幂，这样就不用考虑%2余数的情况
//而且不必担心高次项的系数，因为默认为0
FFT(limit,a,1);
FFT(limit,b,1);
//1表示FFT，-1则是反变换
rep(i,0,limit) a[i] = a[i]*b[i];//转换为点值后直接相乘
FFT(limit,a,-1);//现在变回去
rep(i,0,n+m) printf("%d ",(int)(a[i].x/limit+0.5));//还要除以n的
printf("\n");
}
//P3803 【模板】多项式乘法（FFT）
//https://www.luogu.com.cn/problem/P3803迭代FFT
const double Pi = acos(-1.0);
inline int read(){
char c=getchar();int x=0,f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
struct cplx{
double x,y;
cplx(double x=0,double y=0):x(x),y(y){}
friend cplx operator + (cplx a,cplx b){return cplx(a.x+b.x,a.y+b.y);}
friend cplx operator - (cplx a,cplx b){return cplx(a.x-b.x,a.y-b.y);}
friend cplx operator * (cplx a,cplx b){return cplx(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}
}a[MAXN],b[MAXN];
int la,lb;
int rev[MAXN],lim,len;//len存二进制位数
//和递归FFT的limit不一样,这里的lim在FFT执行中是不变的
inline void FFT(cplx a[],int type){
rep(i,0,lim-1) if(i<rev[i]) swap(a[i],a[rev[i]]);
//按照位逆序后的数字大小排好序,因为是置换所以On就行
rep(dep,1,log2(lim)){//第一层枚举层数
int m = 1<<dep;//得到dep层每组的元素个数
cplx Wn(cos(2.0*Pi/m),type*sin(2.0*Pi/m));//单位根
for(int k=0;k<lim;k+=m){//第二层k表示每个m元组开始的点
cplx w(1,0);
rep(j,0,(m>>1)-1){
cplx t = w*a[k+j+m/2];//蝴蝶操作,两两进行运算
cplx u = a[k+j];
//之前因为这句卡了好久,没这句的话a[k+j]的值改变了,a[k+j+m/2]就错了
a[k+j] = a[k+j]+t;
a[k+j+m/2] = a[k+j]-t;
w = w*Wn;
}
}
}
}
inline void init_rev(){//预处理rev位逆序置换数组
rep(i,0,lim-1) rev[i] = (rev[i>>1]>>1) | ((i&1)<<(len-1));//|和+作用是一样的
//后面几位是上一个子问题的解向右移动一位,第一位即最底层按奇偶得出
}
int main(){
la = read(),lb = read();
rep(i,0,la) a[i].x = read();
rep(i,0,lb) b[i].x = read();
lim = 1,len = 0;
while(lim<=la+lb) lim<<=1,len++;//一定要是2的幂
init_rev();//计算位逆序顺序
FFT(a,1);
FFT(b,1);
rep(i,0,lim-1) a[i] = a[i]*b[i];//点值表示法直接相乘
FFT(a,-1);//现在变回去
rep(i,0,la+lb) printf("%d ",(int)(a[i].x/lim+0.5));//还要除以n的
printf("\n");
}//待改
图论
优先队列优化Dijkstra
#define LINF 1ll<<60
const int MAXN = 2e5+10;
typedef pair<int,ll> pli;
vector<pli> e[MAXN];//first是目标的点，second是距离dis
bool vis[MAXN];
ll d[MAXN];
int n,m,s,t;
void dijkstra(){
rep(i,1,n){
d[i] = LINF;
vis[i] = 0;
}
d[s] = 0;
priority_queue< pli,vector<pli>,greater<pli> >q;//first存d[x],second存x的编号
q.push(make_pair(0,s));
while(!q.empty()){//进行类似bfs的操作
int now = q.top().second;
q.pop();
if(vis[now])continue;//可以看到下面的操作是都先推进去的，所以可能重复遇到now点
vis[now] = 1;
int siz = e[now].size();
for(auto x:e[now]){//遍历now的所有边
int v = x.second;//到达的点
if(d[v]>d[now]+x.first){
d[v] = d[now] + x.first;
q.push(make_pair(d[v],v));//推入优先队列
}
}
}
}
int main(){
cin>>n>>m>>s;
int u,v;
ll dis;
rep(i,1,m){
cin>>u>>v>>dis;
e[u].push_back(make_pair(dis,v));
//e[v].push_back(make_pair(u,dis));//双向通行的情况
}
dijkstra();
rep(i,1,n){
cout<<d[i];//输出到各个点的最短路径
if(i!=n) cout<<' ';
}
} Dinic
struct Edge{
int from,to;
ll cap,flow;
};
int n,m,s,t;//节点数，边数(含反向弧)，源点与汇点编号
vector<Edge> edges;//边长，edges[e]和edges[e^1]互为反向弧
vector<int> G[MAXN];//邻接表，G[i][j]表示节点i的第j条边在edges中的编号
int d[MAXN];//dist层数，即d[i]为起点到i的距离（层数）,同时也起到vis的作用防止重复走
int cur[MAXN];//这个cur是dfs的时候用来省略重复步骤的
void add_edge(int from,int to,ll cap){
edges.push_back((Edge){from,to,cap,0});
edges.push_back((Edge){to,from,0,0});
int siz = edges.size();
G[from].push_back(siz-2);//正向边
G[to].push_back(siz-1);//反向边
}
bool bfs(){
memset(d,-1,sizeof(d));
queue<int> q;
q.push(s);
d[s]=0;//dist(s) = 0
while(!q.empty()){
int x=q.front();
q.pop();
rep(i,0,G[x].size()-1){
Edge &e = edges[G[x][i]];
if(d[e.to]==-1&&e.cap>e.flow){//只考虑残量网络中的弧即这个边还没被填满
d[e.to]=d[x]+1;//标记层次dist(x)
q.push(e.to);
}
}
}
return d[t]!=-1;//找到到t节点的路径则回1，找不到则回0
}
ll dfs(int x,ll a){//DFS除了当前节点x外，还要传入"目前为止所有边的最小残量"即"水流到这里还剩多少"
if(x==t||a==0) return a;//也是很简洁一句话 ，结束增广
ll flow = 0,f;
for(int &i=cur[x];i<G[x].size();i++){//上一次阻塞流已经把cur[x]之前的弧都排除了
Edge &e = edges[G[x][i]];
if(d[x]+1==d[e.to]&&(f=dfs(e.to,min(a,e.cap-e.flow)))>0){
e.flow+=f;
edges[G[x][i]^1].flow-=f;
flow+=f;
a-=f;
if(a==0) break;//这句及时退出很影响效率
}
}
return flow;
}
ll Maxflow(){
ll flow=0;
while(bfs()){
memset(cur,0,sizeof(cur));//因为有新的反向边引入，即"正向边"更新了 ,有些实际上是反,但dfs里面当正的用
flow+=dfs(s,INF);//对当前阻塞流dfs；
}
return flow;
}
int main(){
int u,v;
ll cap;
scanf("%d%d%d%d",&n,&m,&s,&t);
for(int i=1;i<=m;i++){
scanf("%d%d%lld",&u,&v,&cap);
add_edge(u,v,cap);
}
cout<<Maxflow()<<endl;
}
//P3376 【模板】网络最大流 https://www.luogu.com.cn/problem/P3376二分匹配匈牙利
int uN,vN;//u,v的数目
bool g[MAXN][MAXN];//邻接矩阵,一般情况下uv最大范围相同
int linker[MAXN];//存右节点的对象
bool used[MAXN]; //右点是否访问过
bool dfs(int u){
for(int v=0;v<vN;v++){
if(g[u][v]&&!used[v]){//判断是否有边，是否被用过
used[v]=true;//标记访问
if(linker[v]==-1||dfs(linker[v])){
linker[v]=u;//很精妙，记录新配对，在进行dfs后，连接左右节点的边其实方向反了一反
return true;
}
}
}
return false;
}
int hungary(){//匈牙利算法
int res=0;
memset(linker,-1,sizeof(linker));//初始化,因为节点uv从0开始，所以linker初始化为-1
for(int u=0;u<uN;u++){
memset(used,false,sizeof(used));
if(dfs(u)) res++;
}
return res;
}
int main(){
int e;
cin>>uN>>vN>>e;
int u,v;
memset(g,0,sizeof(g));
while(e--){
scanf("%d%d",&u,&v);
g[u][v]=1;
}
cout<<hungary()<<endl;
}
/*匈牙利算法可以解决的问题：
1.二分图的最大匹配数(如婚配问题)
2.最小顶点覆盖------用最少的点覆盖所有的边(如HDOJ禁止早恋,任务安排)
结论：最小顶点覆盖数==最大匹配数量
3. DAG(有向无环图)的最小路径覆盖
(如HDOJ空袭，所有路单行，并且所有街是两个路口相连，已知不会形成回路。问最少空降几个伞兵可以访问所有路口)
拆点法：1拆成1和1',数字x放左节点，x'放右节点
DAG图的最小路径覆盖数 == 节点数(n) - 最大匹配数
*/ kruskal最小生成树
struct Edge{
int u,v,k;
friend bool operator < (Edge a,Edge b){
return a.k<b.k;
}
}edges[MAXM];
int fa[MAXN];
int rankk[MAXN];//树高优化并查集
int find(int x){
if(fa[x]==x) return x;
return fa[x] = find(fa[x]);
}
void merge(int a,int b){
a = find(a);b = find(b);
if(a==b) return;
if(rankk[a]>rankk[b]) fa[b] = a;
else{
fa[a] = b;
if(rankk[a]==rankk[b])rankk[b]++;
}
}
int n,m;
int main(){
cin>>n>>m;
rep(i,1,m) cin>>edges[i].u>>edges[i].v>>edges[i].k;
rep(i,1,n) fa[i] = i,rankk[i] = 0;
sort(edges+1,edges+1+m);
ll res=0;
rep(i,1,m){
if(find(edges[i].u)!=find(edges[i].v)){//检查两点是否在同一集合内
res+=edges[i].k;
merge(edges[i].u,edges[i].v);
}
}
bool flag = 1;
rep(i,2,n){
if(find(n)!=find(n-1)) {flag = 0;break;}
}
if(!flag) cout<<"orz"<<endl;
else cout<<res<<endl;
}
//P3366 【模板】最小生成树 https://www.luogu.com.cn/problem/P3366tarjan求强连通分量
int n;
vector<int> e[MAXN];//存图
int dfn[MAXN],low[MAXN];
int dfncnt;//dfn自增下标
int s[MAXN],tp;//数组模拟栈,tp记录大小
bool in[MAXN];//记录该点是否在栈中
int scc[MAXN],sc;//节点i所在scc的编号,sc记录有几个强连通
int sz[MAXN];//强连通i的大小
int indg[MAXN];//记录缩点后的入度（这题才有的
void tarjan(int u){
low[u]=dfn[u]=++dfncnt;//low初始值为自身dfn
s[++tp]=u;//推u入栈，从1开始
in[u]=1;//记录u点在栈中
for(auto v:e[u]){//访问到新点的情况
if(!dfn[v]){
tarjan(v);
low[u] = min(low[u],low[v]);//用low[v}更新low[u]
}
else if(in[v])//v被访问过，但是在栈中
low[u] = min(low[u],dfn[v]);
}
if(dfn[u]==low[u]){//u是连通分量的根节点
sc++;//强连通数量++
sz[sc] = 0;
while(s[tp]!=u){//u和u之后的点全部出栈
scc[s[tp]] = sc;//这个点包含于第几个强连通
sz[sc]++;//u为根的这个强连通的大小
in[s[tp]] = 0;//出栈
tp--;
}
scc[u] = sc;//给根节点标，属于第sc个强连通
sz[sc]++;
in[u] = 0;
tp--;
}
}
void reset(){
tp = sc = dfncnt =0;
rep(i,1,n){
in[i] = dfn[i] = 0;//low不用清空，sz在之后用到再清空
e[i].clear();
}
}
int main(){
cin>>n;
reset();
int v;
rep(u,1,n){
while(cin>>v&&v!=0) e[u].push_back(v);
}
rep(u,1,n)
if(!dfn[u]) tarjan(u);
rep(i,1,sc) indg[i] = 0;//这个不包含在tarjan里面，是这题记录入度的
rep(u,1,n){
for(auto v:e[u]){
if(scc[u]!=scc[v]) indg[scc[v]]++;
}
}
int res = 0;
rep(i,1,sc){
if(indg[i]==0) res++;
}
cout<<res<<endl;
}
//洛谷P2835 刻录光盘 https://www.luogu.com.cn/problem/P2835#submit拓扑排序
#define LINF 1ll<<60
const int MAXN = 2e5+10;
typedef pair<int,ll> pli;
vector<pli> e[MAXN];//first是目标的点，second是距离dis
bool vis[MAXN];
ll d[MAXN];
int n,m,s,t;
void dijkstra(){
rep(i,1,n){
d[i] = LINF;
vis[i] = 0;
}
d[s] = 0;
priority_queue< pli,vector<pli>,greater<pli> >q;//first存d[x],second存x的编号
q.push(make_pair(0,s));
while(!q.empty()){//进行类似bfs的操作
int now = q.top().second;
q.pop();
if(vis[now])continue;//可以看到下面的操作是都先推进去的，所以可能重复遇到now点
vis[now] = 1;
int siz = e[now].size();
for(auto x:e[now]){//遍历now的所有边
int v = x.second;//到达的点
if(d[v]>d[now]+x.first){
d[v] = d[now] + x.first;
q.push(make_pair(d[v],v));//推入优先队列
}
}
}
}
int main(){
cin>>n>>m>>s;
int u,v;
ll dis;
rep(i,1,m){
cin>>u>>v>>dis;
e[u].push_back(make_pair(dis,v));
//e[v].push_back(make_pair(u,dis));//双向通行的情况
}
dijkstra();
rep(i,1,n){
cout<<d[i];//输出到各个点的最短路径
if(i!=n) cout<<' ';
}
}
//Uva10305 https://vjudge.net/problem/UVA-10305HASH
拉链法
const int med = 1000007;//模数
const int MAXN = 2e6+5;//数据总量
struct Hash_table{
struct Node{
int next,value,key;
}data[MAXN];//数据的总量,从1开始
int head[med],size;//head记录每个哈希值的链表的第一个节点
//size记录节点总数
int f(int key){ return key%med; }//求哈希值
int find(int key){
for(int p = head[f(key)];p;p=data[p].next)//遍历这个哈希值上的链表
if(data[p].key==key) return data[p].value;
return -1;
}
int update(int key,int value){//更新value
for(int p = head[f(key)];p;p=data[p].next)
if(data[p].key==key) return data[p].value = value;
return -1;
}
int add(int key,int value){
if(find(key)!=-1) return -1;//这个值已经被插入了
data[++size] = (Node){head[f(key)],value,key};//从链表头部插入
head[f(key)] = size;//标记该链表的第一个节点
return value;
}
};几何
三个点求圆心
struct point{
double x;
double y;
};
point cal(point a,point b,point c){
double x1 = a.x;double y1 = a.y;
double x2 = b.x;double y2 = b.y;
double x3 = c.x; double y3 = c.y;
double a1 = 2*(x2-x1); double a2 = 2*(x3-x2);
double b1 = 2*(y2-y1); double b2 = 2*(y3-y2);
double c1 = x2*x2 + y2*y2 - x1*x1 - y1*y1;
double c2 = x3*x3 + y3*y3 - x2*x2 - y2*y2;
double rx = (c1*b2-c2*b1)/(a1*b2-a2*b1);
double ry = (c2*a1-c1*a2)/(a1*b2-a2*b1);
return point{rx,ry};
}数学
组合数板子
const int MAXN = 3e5+5;
const int med = 998244353;
ll jc[MAXN];
ll qpow(ll d,ll c){//快速幂
ll res = 1;
while(c){
if(c&1) res=res*d%med;
d=d*d%med;c>>=1;
}return res;
}
inline ll niyuan(ll x){return qpow(x,med-2);}
void initjc(){//初始化阶乘
jc[0] = 1;
rep(i,1,MAXN-1) jc[i] = jc[i-1]*i%med;
}
inline int C(int n,int m){//n是下面的
if(n<m) return 0;
return jc[n]*niyuan(jc[n-m])%med*niyuan(jc[m])%med;
}
int main(){
initjc();
int n,m;
while(cin>>n>>m) cout<<C(n,m)<<endl;
}高斯消元
double a[MAXN][MAXN];
int n,pl;
int main(){
scanf("%d",&n);
rep(i,1,n)
rep(j,1,n+1) scanf("%lf",&a[i][j]);
rep(i,1,n){
pl = i;
while(a[pl][i]==0&&pl<=n) pl++;//找到每列的第一个非0元素
if(pl==n+1){//无解的情况(存在空列
cout<<"No Solution"<<endl;return 0;
}
rep(j,1,n+1) swap(a[i][j],a[pl][j]);//保证i行i列必不是0
double k = a[i][i];//第二步，使a[i][i]变成1
rep(j,1,n+1) a[i][j]/=k;//i行所有元素除a[i][i]
rep(ii,1,n){
if(ii==i) continue;//枚举不同的两行
double ki = a[ii][i];
rep(m,1,n+1) a[ii][m]-=ki*a[i][m];
}
}
rep(i,1,n) printf("%.2lf\n",a[i][n+1]);
}
//洛谷P3389 【模板】高斯消元法 https://www.luogu.com.cn/problem/P3389矩阵快速幂
int n;
const ll mod = 998;
struct Matrix{
ll a[MAXN][MAXN];
Matrix(ll x=0){//感觉是特别好的初始化,从hjt那里学(抄)来的
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
a[i][j]=x*(i==j);//这句特简洁
}
}
}
Matrix operator *(const Matrix &b)const{//通过重载运算符实现矩阵乘法
Matrix res(0);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
for(int k=0;k<n;k++){
ll &ma = res.a[i][j];
ma = (ma+a[i][k]*b.a[k][j])%mod;
}
}
}
return res;
}
};
Matrix qpow(Matrix d,ll m){//底数和幂次数
Matrix res(1);//构造E单位矩阵
while(m){
if(m&1){
m--;//其实这句是可以不要的
res=res*d;
}
d=d*d;
m>>=1;
}
return res;
}
int main(){
int p;
Matrix inp;
cin>>n>>p;
for(int i=-0;i<n;i++){
for(int j=0;j<n;j++){
scanf("%lld",&inp.a[i][j]);
}
}
Matrix res = qpow(inp,p);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cout<<res.a[i][j];
if(j!=n-1) cout<<' ';
}
cout<<endl;
}
}数论
线性求逆元
void init(int p){
inv[1] = 1;
for(int i=2;i<=n;i++){
inv[i] = (ll)(p-p/i)*inv[p%i]%p;
}
}单个欧拉函数
void init(int p){
inv[1] = 1;
for(int i=2;i<=n;i++){
inv[i] = (ll)(p-p/i)*inv[p%i]%p;
}
}EXCRT扩展中国剩余
template<class T>
void wt(T x){//快写
if(x < 0) putchar('-'), x = -x;
if(x >= 10) wt(x / 10);
putchar('0' + x % 10);
}
void Exgcd(ll a,ll b,ll &d,ll &x,ll &y){//扩展欧几里得
if(!b){d=a;x=1;y=0;}
else{Exgcd(b,a%b,d,y,x);y-=x*(a/b);}//先交换了xy的位置，实现y1=x2-(a/b)*x2
}
inline ll mul(ll a,ll b,ll mo){//取模乘法
return ((a%mo)*(b%mo)%mo+mo)%mo;
}
const int MAXN = 1e5+5;
ll c[MAXN],m[MAXN];//每组同余式的余数和模数
int n;
ll Excrt(ll m[],ll c[],int n){
ll mnow = m[1],cnow = c[1];//记录每次合成后的模数余数
rep(i,2,n){
ll p1,p2,gcdd;
ll m1 = mnow,m2 = m[i];//m1p1+c1 = m2p2+c2
ll dc = (c[i]-cnow%m2+m2)%m2;//dc在保证同余的情况下变成最小的正数
Exgcd(m1,m2,gcdd,p1,p2);
if(dc%gcdd) {cout<<i<<endl;return -1;}
p1 = mul(p1,dc/gcdd,m2/gcdd);//p1存的实际是p1*m1,这里的模数比较讲究
//一会儿要对lcm(m1,m2)取模,最终结果是[p1*m1*(dc/gcdd)] % [m2/gcdd*m1]
//m1还没乘上去,这时候先对m2/gcdd取模
cnow += p1*m1;//更新cnow和mnow
mnow = m1/gcdd*m2;
cnow = (cnow%mnow+mnow)%mnow;
}
return cnow;
}
int main(){
cin>>n;
rep(i,1,n) read(m[i]),read(c[i]);
wt(Excrt(m,c,n));
}
//洛谷P4777 【模板】扩展中国剩余定理（EXCRT）
//https://www.luogu.com.cn/problem/P4777EXGCD扩展欧几里得
ll Exgcd(ll a,ll b,ll &x,ll &y){
if(!b){x=1;y=0;return a;}//边界条件结束递归
ll d = Exgcd(b,a%b,x,y);//gcd
ll t = x;
x=y;y=t-(a/b)*y;//通过x2y2求得x1y1,层层返回
return d;
}
//紫书里面刘汝佳的简短的版本
void Exgcd(ll a,ll b,ll &d,ll &x,ll &y){//不同的是，这里的d使用引用来实现
if(!b){d=a;x=1;y=0;}
else{Exgcd(b,a%b,d,y,x);y-=x*(a/b);}//先交换了xy的位置，实现y1=x2-(a/b)*x2
} 字符串
AC自动机
统计是否出现
const int MAXN = 1e6+5;
inline int idx(char c){return c-'a';}
struct Node{
int son[26],flag,fail;
}trie[MAXN*10];
int n,cntt;
string s;
queue<int> q;
void insert(string &s){//字典树插入模式串
int siz = s.size(),v,u = 1;//根节点开始
rep(i,0,siz-1){
v = idx(s[i]);
if(!trie[u].son[v]) trie[u].son[v] = ++cntt;
u = trie[u].son[v];
}
trie[u].flag++;//记数
}
void getfail(){//处理失配指针
rep(i,0,25) trie[0].son[i] = 1;//虚节点0
q.push(1);trie[1].fail = 0;
//建一个虚节点0号节点,将1的所有儿子指向1，然后1的fail指向0就OK了
int u,v,ufail;
while(!q.empty()){
u = q.front();q.pop();
rep(i,0,25){
v = trie[u].son[i];
ufail = trie[u].fail;
if(!v){trie[u].son[i]=trie[ufail].son[i];continue;}
//如果这个分支不满足，则会和失配的情况类似去跳转
trie[v].fail = trie[ufail].son[i];
//((他父亲节点)的失配指针指向的节点)的(和这个节点字母相同的儿子)
q.push(v);
}
}
}
int query(string &s){//匹配
int siz = s.size(),u = 1,v,k,ans = 0;
rep(i,0,siz-1){
v = idx(s[i]);
k = trie[u].son[v];//k用来跳fail
while(k&&trie[k].flag!=-1){//找到了没标记的单词
ans += trie[k].flag;trie[k].flag = -1;//计数,并标记走过
k = trie[k].fail;//跳fail,如果一个串匹配成功,那它的fail一定也能匹配
}
u = trie[u].son[v];
}
return ans;
}
int main(){
cntt = 1;//初始化cnt
cin>>n;
string hc;
rep(i,1,n){
cin>>s;insert(s);
}
getfail();
cin>>s;
cout<<query(s)<<endl;
}
//P3808 【模板】AC自动机（简单版）https://www.luogu.com.cn/problem/P3808
//https://www.luogu.com.cn/blog/juruohyfhaha/solution-p3808统计出现次数(比较慢一点)
const int MAXN = 1e5+5;
int jdbh[MAXN];//记录第i个模式串对应的节点编号
int cntcx[MAXN];//记录第i个模式串出现的次数
inline int idx(char c){return c-'a';}
struct Node{
int son[26],flag,fail;//cnt记录次数,flag记录编号
void clr(){
memset(son,0,sizeof(son));
flag=0;
}
}trie[MAXN*10];
int n,cntt;//cntt记录总点数
string s,ms[166];
int maxx;
queue<int>q;
inline void insert(string &s,int num){
int siz = s.size(),v,u=1;
rep(i,0,siz-1){
v = idx(s[i]);
if(!trie[u].son[v]){trie[u].son[v] = ++cntt;trie[cntt].clr();}
u = trie[u].son[v];
}
trie[u].flag = num;//标记为单词,flag记录编号
//保证每个模式串只出现一次
cntcx[num] = 0;
jdbh[num] = u;//记录当前单词对应的节点编号
}
inline void getfail(){
rep(i,0,25) trie[0].son[i] = 1;
trie[0].flag = 0;
q.push(1);
trie[1].fail = 0;
int u,v,ufail;
while(!q.empty()){
u = q.front();q.pop();
rep(i,0,25){
v = trie[u].son[i];
ufail = trie[u].fail;
if(!v){trie[u].son[i]=trie[ufail].son[i];continue;}//画好一条跳fail的路
trie[v].fail = trie[ufail].son[i];
q.push(v);
}
}
}
inline void query(string &s){
int siz = s.size(),u = 1,v,k;
rep(i,0,siz-1){
v = idx(s[i]);
k = trie[u].son[v];
while(k){
if(trie[k].flag){
cntcx[trie[k].flag]++;//计数
maxx = max(maxx,cntcx[trie[k].flag]);
}
k = trie[k].fail;//跳fail
}
u = trie[u].son[v];//这一句其实也有跳fail的功能，很精妙
}
}
inline void solve(){
cntt = 1;
trie[0].clr();
trie[1].clr();
rep(i,1,n){
cin>>ms[i];
insert(ms[i],i);
}
getfail();
cin>>s;
maxx = 0;
query(s);
cout<<maxx<<endl;
rep(i,1,n){
if(cntcx[i]==maxx) cout<<ms[i]<<endl;
}
}
int main(){
while(cin>>n&&n!=0) solve();
}
//洛谷 P3796 【模板】AC自动机（加强版）
//https://www.luogu.com.cn/problem/P3796KMP字符串匹配
const int MAXN = 2e6+5;
int pi[MAXN];//MAXN记得开大一点,因为这里要存到m+n+1长度的
vector<int> res;//储存答案
void getpi(const string &s){ //求s的前缀函数
pi[0]=0;
int j=0;
rep(i,1,s.length()-1){
while(j>0&&s[i]!=s[j]) j=pi[j-1];//找到合适且最长的j
if(s[i]==s[j])j++;//能成功匹配的情况
pi[i]=j;
}
}
void kmp(string s,string t){ //在主串t中找模式串s
getpi(s+'#'+t);
int n=(int)s.length(),m=(int)t.length();
rep(i,n+1,m+n+1-1)
if(pi[i]==n) res.push_back(i-2*s.size()); //i-2n计算得左端点
}字符串哈希
双哈希判断是否相等
typedef pair<ull,ull> pll;
const int MAXN = 1e4+5;
const int M1 = 1e9+7;//第一个模数
const int M2 = 1e9+9;//第二个模数
const int b = 131;
int n;
pll a[MAXN];
pll gethash(string s){
ull res1=0,res2=0;
int siz = s.length();
rep(i,0,siz-1){
res1=(res1*b%M1+s[i])%M1;//i位乘以b^i
res2=(res2*b%M2+s[i])%M2;//f(s)=Σ s[i] * b^i;
}
return make_pair(res1,res2);
}
int main(){
cin>>n;
string s;
rep(i,1,n){
cin>>s;a[i]=gethash(s);
}
sort(a+1,a+n+1);
int res = 1;
rep(i,2,n){
if(a[i]!=a[i-1]) res++;
}
cout<<res<<endl;
}配合快速幂取子串的哈希值
const int b = 131;
const int MAXN = 1e5 + 5;
typedef unsigned long long ull;
ull h[MAXN], pw[MAXN]; // h[k]存储字符串前k个字母的哈希值, pw[k]存储 b^k mod 2^64
//这里的模数M取的就是ull的上限2^64
char str[MAXN];
void init(int n){//初始化
pw[0] = 1;
for (int i = 1; i <= n; i ++ ) {
h[i] = h[i-1]*b + str[i];//做每个前缀的哈希值
pw[i] = pw[i-1]*b;//预处理b^k的值
}
}
// 计算子串 str[l ~ r] 的哈希值
ull get(int l, int r) {
return h[r] - h[l-1]*pw[r-l+1];
}
int main() {
int n, m;
scanf("%d%d%s",&n,&m,str+1);//这样读入字符串第一位从1开始
init(n);
while (m--) {
int l1,r1,l2,r2;
scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
if(get(l1,r1)!=get(l2,r2))
printf("No\n");
else printf("Yes\n");
}
return 0;
}
//ACWing 841 给两个区间查询这两个子串是否相同Trie字典树
#define MAXN 10000
const int maxnode=2e6+5;
const int sigma_size=26;//字母开26，如果是数字之类的则开10
char s[MAXN];
struct Trie{
int ch[maxnode][sigma_size];
int val[maxnode];
int sz;
Trie(){sz=1;memset(ch[0],0,sizeof(ch[0]));}//初始化，此时只有根节点
int idx(char c){
return c-'a';//同理如果是数字则换成c-'0'
}
void insert(char *s,int v){
int u=0,n=strlen(s);
for(int i=0;i<n;i++){
int c=idx(s[i]);
if(!ch[u][c]){//节点不存在(u没有子节点字母为c)这个u和c的意义全然不同,u是节点编号,c是字符编号
memset(ch[sz],0,sizeof(ch[sz]));
val[sz]=0;//中间节点，附加信息为0，当然也可以用其他的来标记比如-1
ch[u][c]=sz++;//画好边，并且总结点数++
}
u=ch[u][c];//光标往下走
}//这里出来就是u已经到单词节点(即一个单词的末尾字符)上了
val[u] = v;//insert时的第二个参数v,可以附加信息
}
bool find(char *s,int len){//查找串s长度不超过len的前缀,改一改成int也可以返回附加值
int u=0;
for(int i=0;i<len;i++){
if(s[i]=='\0') break;
int c=idx(s[i]);
if(!ch[u][c]) break;
u=ch[u][c];
if(val[u]!=0) return true;
}
return false;
}
}T;//之前因为T定义在main里面所以一直运行不了，发现这个结构体和数组有点类似
//定义为全局函数可以开得更大！
int main(){
int n;
scanf("%d",&n);
getchar();
Trie T;
while(n--){
scanf("%s",s);
getchar();
T.insert(s,1);
}
scanf("%d",&n);
getchar();
while(n--){
scanf("%s",s);
getchar();
if(T.find(s,strlen(s))) cout<<"yes!"<<endl;
else cout<<"no!"<<endl;
}
}动态规划DP
数位DP
int l,r;
const int MAXN = 25;
int dp[MAXN][2];//第二维记录前面一个是否为2
int a[MAXN];
int n,m;
int dfs(int pos,bool stat,int pre,bool limit){
//limit记录之前是否都在上界，state记录之前的是不是6(记忆化作第二维)，pre记录上一个数字
if(pos==-1) return 1;
if(!limit&&dp[pos][stat]!=-1) return dp[pos][stat];
int up = limit?a[pos]:9;//如果前面的都在上界则只能到a[pos]
int ans = 0;
for(int i=0;i<=up;i++){
if(pre==6&&i==2) continue;//62的情况
if(i==4) continue;
ans += dfs(pos-1,i==6,i,limit&&i==a[pos]);
}
if(!limit) dp[pos][stat] = ans;
return ans;
}
int solve(int x){
//先按位转化到数组
int px = 0;
while(x){
a[px++] = x%10;
x/=10;
}
memset(dp,-1,sizeof(dp));//清空记忆化数组
return dfs(px-1,0,-1,1);
}
int main(){
while(cin>>l>>r){
if(l==0&&r==0) break;
//cout<<solve(r)<<' '<<solve(l-1)<<endl;
cout<<solve(r)-solve(l-1)<<endl;
}
}
//HDOJ2089 不要62其他
母函数
#include<iostream>
using namespace std;
#define rep(i,a,b) for(int (i)=a;i<=b;i++)
const int MAXN = 1e4;
int c1[MAXN+1];
int c2[MAXN+1];
int main(){
int n;
while(cin>>n){
for(int i=0;i<=n;i++){//初始化
c1[i]=0;
c2[i]=0;
}
for(int i=0;i<=n;i++){
c1[i]=1;//面值为一元的
}
for(int i=2;i<=n;i++){//枚举邮票的面值(一共有几组括号
for(int j=0;j<=n;j++){//枚举左边次数为0到次数为n的项
for(int k=0;j+k<=n;k+=i){//右边的乘过来，枚举放几枚
//次数大于n的就不用管了
c2[j+k]+=c1[j];
}
}
for(int i=0;i<=n;i++){//最左边两个括号完成处理
c1[i]=c2[i];//把c2算出来的值挪到左边作为下一次的左边
c2[i]=0;//清空c2记录下一次括号相乘的结果
}
}
cout<<c1[n]<<endl;
}
} 并查集
int par[MAXN];//记录父亲节点
int rank[MAXN];//记录树高,根节点(祖先节点)那层是不算进去的
void init(int n){
for(int i=0;i<n;i++){
par[i]=i;
rank[i]=0;
}
}
int find(int x){//查询根操作，同时进行路径压缩
if(par[x]==x) return x;
else return par[x]=find(par[x]);//这句很精简,在递归查询根节点的同时路i压缩
}
//虽然路径压缩的操作会对树高产生影响，导致rank的数值不准确，但这样还是能有效地提高运行效率的
void merge(int x,int y){
x=find(x);y=find(y);
if(x==y) return;///如果已经具有相同的祖先，则不进行合并操作
if(rank[x]<rank[y]) par[x]=y;//y树比x树高的情况，把x并为y的儿子节点
else{//y比x高，或同高的情况下，把y并为x的儿子节点
par[y]=x;
if(rank[x]==rank[y]) rank[x]++;//如果合并的两树同高，则合并后树高+1;
}
}
int main(){
int n,m;
cin>>n>>m;
init(n);
int a,b;
while(m--){
cin>>a>>b;
merge(a,b);
}
cin>>m;
while(m--){
cin>>a>>b;
if(find(a)==find(b)) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
}
//路径压缩+树高优化莫队
普通莫队
const int MAXN = 5e4+5;
int cnt[MAXN];//记录数字在区间[l,r]内出现的次数
int pos[MAXN],a[MAXN];
ll ans[MAXN];
int n,m,k,res;
struct Q{
int l,r,k;//k记录原来的编号
friend bool operator < (Q x,Q y){//同一个分块内r小的排前面;不同分块则按分块靠前的
return pos[x.l]==pos[y.l]?x.r<y.r:pos[x.l]<pos[y.l];
//return (pos[a.l]^pos[b.l])?pos[a.l]<pos[b.l]:((pos[a.l]&1)?a.r<b.r:a.r>b.r);
//这条第一个和==是一样的,后面的是对于左端点在同一奇数块的区间，右端点按升序排列，反之降序
}
}q[MAXN];
void Add(int pos){
res -= cnt[a[pos]]*cnt[a[pos]];
cnt[a[pos]]++;
res += cnt[a[pos]]*cnt[a[pos]];
}
void Sub(int pos){
res -= cnt[a[pos]]*cnt[a[pos]];
cnt[a[pos]]--;
res += cnt[a[pos]]*cnt[a[pos]];
}
int main(){
cin>>n>>m>>k;//k为数字范围
memset(cnt,0,sizeof(cnt));
int siz = sqrt(n);//每个分块的大小
rep(i,1,n){
cin>>a[i];
pos[i] = i/siz;//分块
}
rep(i,1,m){
cin>>q[i].l>>q[i].r;
q[i].k = i;//记录原来的编号,用于打乱顺序后的还原
}
sort(q+1,q+1+m);
res = 0;//初始化res
int l = 1,r = 0;//当前知道的区间
//因为是闭区间,如果是[1,1]的话则一开始就包含一个元素了
rep(i,1,m){//莫队的核心,注意加减的顺序
while(q[i].l<l) Add(--l);
while(q[i].l>l) Sub(l++);
while(q[i].r<r) Sub(r--);
while(q[i].r>r) Add(++r);
ans[q[i].k] = res;
}
rep(i,1,m) cout<<ans[i]<<endl;
}
//洛谷P2709 小B的询问
//https://www.luogu.com.cn/problem/P2709带修莫队
int cnt[1000010] = {0};
const int MAXN = 2e5+5;
int a[MAXN],b[MAXN];//a读入一开始的序列,b记录修改后的
int pos[MAXN];//分块
int cq,cr;//统计查询修改次数
int R[MAXN][3];//0记位置,1记原本的值,2记修改后的值
ll res;
int ans[MAXN];//记录结果
int n,m;
void Add(int x){if(cnt[x]==0)res++;cnt[x]++;}//带修莫队的add和sub有区别
void Sub(int x){if(cnt[x]==1)res--;cnt[x]--;}
struct Q{
int l,r,k,t;
friend bool operator < (Q a,Q b){
return (pos[a.l]^pos[b.l])?pos[a.l]<pos[b.l]:((pos[a.r]^pos[b.r])?a.r<b.r:a.t<b.t);
//增加第三关键字,询问的先后顺序,用t或者k应该都行
}
}q[MAXN];
int main(){
cin>>n>>m;
cq = cr = 0;
int siz = pow(n,2.0/3.0);//这么分块最好,别问
rep(i,1,n){
cin>>a[i];
b[i]=a[i];
pos[i] = i/siz;
}
char hc;
rep(i,1,m){//读入修改和询问
cin>>hc;
if(hc=='Q'){
cin>>q[cq].l>>q[cq].r;
q[cq].k=cq;q[cq].t=cr;//注意这时候R[cr]还是没有的,这次询问是在R[cr-1]之后的
cq++;
}
else{
cin>>R[cr][0]>>R[cr][2];
R[cr][1] = b[R[cr][0]];
b[R[cr][0]] = R[cr][2];//在b数组中记录更改
cr++;
}
}
sort(q,q+cq);
int l=1,r=0,sjc=0;//时间戳
res = 0;
rep(i,0,cq-1){
while(sjc<q[i].t){
if(l<=R[sjc][0]&&R[sjc][0]<=r)//判断修改是否在该区间内
Sub(R[sjc][1]),Add(R[sjc][2]);
a[R[sjc][0]] = R[sjc][2];//在a上也进行更改
sjc++;
}
while(sjc>q[i].t){
sjc--;
if(l<=R[sjc][0]&&R[sjc][0]<=r)//判断修改是否在该区间内
Sub(R[sjc][2]),Add(R[sjc][1]);
a[R[sjc][0]] = R[sjc][1];//在a上也进行更改
}
while(l>q[i].l) Add(a[--l]);
while(l<q[i].l) Sub(a[l++]);
while(r<q[i].r) Add(a[++r]);
while(r>q[i].r) Sub(a[r--]);
ans[q[i].k] = res;
}
rep(i,0,cq-1) cout<<ans[i]<<endl;
}
//洛谷P1903 [国家集训队]数颜色 / 维护队列
//https://www.luogu.com.cn/problem/P1903扫描线Scanline
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define ll long long
#define ls (x<<1)
#define rs (x<<1|1)//这种方法感觉还挺好的
const int MAXN = 2e5+5;//这里要开n的两倍
//线结构体
struct Line{
ll l,r,h;
int qz;//记录位置和权值
bool operator < (Line &rhs){
return h < rhs.h;
}
}line[MAXN];
int n;
ll x1,y1,x2,y2;
ll X[MAXN];
//线段树
struct Segt{
int l,r;//是X的下标,即离散化后的
int sum;//sum是被完全覆盖的次数
ll len;//len是区间内被盖住的长度
//因为每次查询都是查询根节点,所以这边不需要懒惰标记
}t[MAXN<<3];//一个边有两个点,所以这里要开8倍
void build(int x,int l,int r){
t[x].l = l;t[x].r = r;
t[x].len = t[x].sum = 0;
if(l==r) return;//到了叶子节点
int mid = (l+r)>>1;
build(ls,l,mid);
build(rs,mid+1,r);
}
void push_up(int x){
int l = t[x].l,r = t[x].r;
if(t[x].sum) t[x].len = X[r+1]-X[l];//x的区间是X[l]到X[r+1]-1
else t[x].len = t[ls].len + t[rs].len;//合并儿子的信息
}
void update(int x,int L,int R,int v){//这里的LR存的是实际值
//这里如果是线段L,R,线段树上是L到R-1的部分维护
int l = t[x].l,r = t[x].r;
if(X[r+1]<=L||R<=X[l]) return;//加等于,不然会搞到无辜的线
if(L<=X[l]&&X[r+1]<=R){
t[x].sum += v;//修改覆盖次数
push_up(x);
return;
}
update(ls,L,R,v);
update(rs,L,R,v);
push_up(x);
}
int main(){
cin>>n;
rep(i,1,n){
cin>>x1>>y1>>x2>>y2;
X[2*i-1] = x1,X[2*i] = x2;//一会儿离散化要用的,这里存实际值
line[2*i-1] = Line{x1,x2,y1,1};//开始的线
line[2*i] = Line{x1,x2,y2,-1};//结束的线
}
n<<=1;//line的数量是四边形数量的2倍
sort(line+1,line+1+n);
sort(X+1,X+1+n);
int tot = unique(X+1,X+n+1)-(X+1);//去除重复相邻元素,并且tot记录总数
build(1,1,tot-1);//为什么是tot-1?
//因为线段树只需要维护X[1]到X[tot]-1这一段的,实际长度是向右贴的
ll res = 0;
rep(i,1,n-1){//每次高度是line[i+1].h-line[i].h,所以是到n-1就行
update(1,line[i].l,line[i].r,line[i].qz);//扫描线加入线段树
res += t[1].len*(line[i+1].h-line[i].h);
}
cout<<res<<endl;
}
//洛谷P5490 【模板】扫描线
//https://www.luogu.com.cn/problem/P5490CDQ分治
处理三位偏序问题，以luogu陌上花开为例：https://www.luogu.com.cn/problem/P3810
序列上每个node有a,b,c三个属性，定义函数f(i)为对位置i的序列，存在多少个$j\leq i$使得$a_j\leq a_i,b_j\leq b_i,c_j\leq c_i$。统计完成后问对每个$0<d<n$，有多少个$i$使得$f(i)=d$.
方法是先对第一维度a进行排序,之后第二维满足$b_j\leq b_i$的每一对i,j，我们分成三种情况:ij都在左半边，ij都在右半边，i在左半边j在右半边。
前两个通过递归求解，求解完左右子区间后，根据第二关键字对两个子区间分别进行排序，这样一来左半边的a一定小于右半边的a，而且两个区间内的b都呈递增。我们用双指针的方法，右边的pxi每往右移动一次，左边的pxj对应移动，并且把这些j都推入树状数组中，之后根据pxi指向的节点的c属性，查询线段树中c比c[pxi]小的数量即可。
#include<iostream>
#include<algorithm>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
const int MAXN = 214514;
struct node{
int a,b,c,cnt,ans;
}s1[MAXN],s2[MAXN];
int ans[MAXN];//存对每个d,f[i]==d的i数量
int n,k,m;
//树状数组
int mx;
int treec[MAXN];
inline int lowbit(int x){return x&-x;}
inline void add(int x,int t){
while(x<=mx) treec[x]+=t,x+=lowbit(x);
}
inline int query(int x){
int ret = 0;
while(x) ret+=treec[x],x-=lowbit(x);
return ret;
}
//cdq分治
bool cmp1(node x,node y){//以a为关键字从小打到排序
if(x.a==y.a){
if(x.b==y.b) return x.c<y.c;
return x.b<y.b;
}
return x.a<y.a;
}
bool cmp2(node x,node y){//根据b排序,便只剩下c的顺序没有满足
if(x.b==y.b) return x.c<y.c;
return x.b<y.b;
}
void cdq(int l,int r){
if(l==r) return;
int mid = (l+r)>>1;
//处理前两种情况:ij同在左/右
cdq(l,mid);cdq(mid+1,r);
//处理第三种情况:i在左j在右
sort(s2+l,s2+mid+1,cmp2);
sort(s2+mid+1,s2+r+1,cmp2);
int pxj=l,pxi=mid+1;//双指针,对应pxi的移动把pxj插入树状数组中
for(pxi=mid+1;pxi<=r;pxi++){
while(s2[pxj].b<=s2[pxi].b&&pxj<=mid){
add(s2[pxj].c,s2[pxj].cnt);//带次数插入树状数组中
pxj++;
}
s2[pxi].ans+=query(s2[pxi].c);
//查询树状数组中c比他小的
}
rep(j,l,pxj-1) add(s2[j].c,-s2[j].cnt);//之前错在这里,注意只有pxj前面的才被加过,pxj没有
//遍历pxj走过的区间,清空树状数组
}
int main(){
cin>>n>>k;
m=0,mx=k;//树状数组的最大数字(类似权值线段树)
rep(i,1,n) cin>>s1[i].a>>s1[i].b>>s1[i].c;
sort(s1+1,s1+1+n,cmp1);//以a为关键字从小到大排序
int tmp=0;//当前这个项出现了几次
rep(i,1,n){//合并相同的项并且记录出现次数进cnt
tmp++;//当前项出现了几次
if(s1[i].a!=s1[i+1].a||s1[i].b!=s1[i+1].b||s1[i].c!=s1[i+1].c){//判断两个node是否不同
s2[++m]=s1[i];//m统计元素个数
s2[m].cnt = tmp;
tmp = 0;
}
}
cdq(1,m);//递归计算
//题目问的是f(x)=满足条件ij对数,对应每个x有几个,把结果存到ans[x]中
rep(i,1,m) ans[s2[i].ans+s2[i].cnt-1]+=s2[i].cnt;
//s2[i].cnt-1是这些数字自己之间满足的对数
rep(i,0,n-1) cout<<ans[i]<<endl;
}
//洛谷P3810陌上花开
//https://www.luogu.com.cn/problem/P3810
