毕生所学
liuchijun
·
·
算法·理论
毕生所学，缺点请补充\
$update12.07$补充离散化\
$update01.20$补充tarjan\
$update02.22$补充ST表\
$update03.29$补充AC机\
$update26.1.30$改善tarjan,补充线性筛素数，线性求积性函数\
$update26.7.15$补充退背包，主席树\
$update26.8.11$补充PAM\
$update26.8.29$复习初赛时发现“树状数组”是线段树，现在进行补充，感谢 @__ACcident__
```cpp
//快速幂
long long qpow(int x,int n)
{
long long res = 1;
while(n)
{
if(n & 1)
res = 1ll * x * x % mod;
x = 1ll * x * x % mod;
n >>= 1;
}
return res;
}
//二分
int search(int l,int r,int x)
{
int mid,res = -1;
while(l <= r)
{
mid = (l + r) / 2;//l+(r-l)>>1
if(a[mid] >= x)
res = mid,
r = mid - 1;
else
l = mid + 1;
}
return res;
}
//建树并且中序遍历
const int N = 1010;
struct binarytree{
int val,lc,rc;
}tree[N];
void inorder(int node)//lc -> rt -> rc
{
if(node == 0)
return;
inorder(tree[node].lc);
cout << node.val << ' ';
inorder(tree[node].rc);
}
//dfs
void dfs(int u,int fa)
{
dep[u] = 1;
for(auto ed : G[u])
{
int v = ed.v;
if(v == fa)
continue;
dep[v] = dep[u] + 1;
dfs(v,u);
}
}
//bfs
vis[s]=true;
queue<int>q;
q.push(s);
while(!q.empty()){
int u=q.front();
cout<<u<<' ';
q.pop();
for(int i=head[u];i;i=e[i].next){
int v=e[i].v;
if(vis[v])
continue;
vis[v]=true;
q.push(v);
}
}
//floodfill
const int dx[4]={-1,0,0,1};
const int dy[4]={0,-1,1,0};
void dfs(int x,int y,int newcolor int oldcolor){
c[x][y]=newcolor;
for(int i=0;i<4;++i){
int nx=x+dx[i],ny=y+dy[i];
if(nx<1||nx>n||ny<1||ny>n)
continue;
if(c[nx][ny]!=oldcolor)
continue;
dfs(nx,ny,newcolor,oldcolor);
}
}
//前缀和求区间和
for(ll i=1;i<=n;i++)
cin>>a[i],s[i]=s[i-1]+a[i];
cin>>m;
for(ll i=1;i<=m;i++)
cin>>l>>r,cout<<s[r]-s[l-1]<<endl;
//树状数组及加、求和操作
void add(int x,int k)
{
while(x <= n)
c[x] += k,
x += lowbit(x);
}
int getsum(int x)
{
int res = 0;
while(x)
res += c[x],
x -= lowbit(x);
return res;
}
//求逆序对
void msort(int b,int e)
{
if(b==e)
return;
int mid=(b+e)/2,i=b,j=mid+1,k=b;
msort(b,mid),msort(mid+1,e);
while(i<=mid&&j<=e)
if(a[i]<=a[j])
c[k++]=a[i++];
else
c[k++]=a[j++],ans+=mid-i+1;
while(i<=mid)
c[k++]=a[i++];
while(j<=e)
c[k++]=a[j++];
for(int l=b;l<=e;l++)
a[l]=c[l];
}
//迪杰斯特拉算法
struct edge{
int v,w;
};
struct node{
int dis,u;
bool operator >(const node& a)const{
return dis>a.dis;
}
};
vector<edge>e[N];
int dis[N],vis[N];
priority_queue<node,vector<node>,greater<node>>q;
void dijkstra(int s){
memset(dis,0x3f,sizeof(dis));
dis[s]=0;
q.push({0,s});
while(!q.empty()){
int u=q.top().u;
q.pop();
if(vis[u])continue;
vis[u]=1;
for(auto ed:e[u]){
int w=ed.w,v=ed.v;
if(dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
q.push({dis[v],v});
}
}
}
}
//普利姆算法
struct e{
ll v,w,x;
}e[M*2];
ll n,m,h[N],cnte;
void addedge(ll u,ll v,ll w)
{e[++cnte]={v,w,h[u]},h[u]=cnte;}
struct s{
ll u,d;
};
bool operator<(const s&x,const s&y){return x.d>y.d;}
priority_queue<s>q;
ll dis[N];
bool vis[N];
ll res=0,cnt=0;
void prim(){
memset(dis,0x3f,sizeof(dis));
dis[1]=0;
q.push({1,0});
while(!q.empty()){
if(cnt>=n)
break;
ll u=q.top().u,d=q.top().d;
q.pop();
if(vis[u])continue;
vis[u]=true;
++cnt;
res+=d;
for(ll i=h[u];i;i=e[i].x){
ll v=e[i].v,w=e[i].w;
if(w<dis[v]){
dis[v]=w,q.push({v,w});
}
}
}
}
//链式前向星
struct node{
ll to;
ll w;
ll nxt;
}e[maxn];
ll head[maxn],cnt;
void addedge(ll u,ll v,ll w){
e[cnt].to=v;
e[cnt].w=w;
e[cnt].nxt=head[u];
head[u]=cnt++;
}
void visit(ll u){
for(ll i=head[u];i;i=e[i].nxt){
int v=e[i].v;
int w=e[i].w;
}
}
//离散化 int arr[n+1]
for(int i=1;i<=n;i++)//step1
tmp[i]=arr[i];
sort(tmp+1,tmp+n+1);//step2
//int len=unique(tmp+1,tmp+n+1)-(tmp+1);//step3
ll quchong(ll* arr,ll n)//等价于unique step3
{
int k=1;
for (int i=2;i<=n;i++)
if (arr[i]!=q[k]) arr[++k]=q[i];
return k;
}
//for(int i=1;i<=n;i++)
// arr[i]=lower_bound(tmp+1,tmp+len+1,arr[i])-tmp;//step4
ll binary_search(ll l,ll r,ll x)//binarysearch step4
{
ll m;
while (l<=r)
{
m=l+r>>1;
if (b[m]==x) return m;
if (b[m]<x) l=m+1;
if (b[m]>x) r=m-1;
}
}
//离散化 vector<int>arr
vector<int>tmp(arr);//step1
sort(tmp.begin(),tmp.end());//step2
tmp.erase(unique(tmp.begin(),tmp.end()),tmp.end());//step3
for(int i=0;i<n;i++)
arr[i]=lower_bound(tmp.begin(),tmp.end(),arr[i])-tmp.begin();//step4
//tarjan
class graph{
private :
vector <vector <int> > G,ans;
vector <int> low,dfn,id,ind;
vector <bool> instk;
stack <int> stk;
int t = 0,cnt = 0,n;
public :
graph(int n) : n(n),G(n + 1),low(n + 1,-1),dfn(n + 1,-1),id(n + 1,-1),ind(n + 1,0),instk(n + 1,false){};
void addedge(int u,int v)
{
G[u].push_back(v);
}
void tarjan(int u)
{
dfn[u] = low[u] = ++t;
stk.push(u);
instk[u] = true;
for(int v : G[u])
{
if(dfn[v] == -1)
{
tarjan(v);
low[u] = min(low[u],low[v]);
}
else
if(instk[v])
low[u] = min(low[u],dfn[v]);
}
if(low[u] == dfn[u])
{
int node;
do
{
node = stk.top();
stk.pop();
instk[node] = false;
id[node] = cnt;
}while(node != u);
cnt++;
}
}
void visit()
{
for(int i = 1;i <= n;i++)
if(dfn[i] == -1)
tarjan(i);
}
void build()
{
ans.resize(cnt);
for(int u = 1;u <= n;u++)
for(int v : G[u])
if(id[u] != id[v])
ans[id[u]].push_back(id[v]);
for(int i = 0;i < cnt;i++)
sort(ans[i].begin(),ans[i].end()),
ans[i].erase(unique(ans[i].begin(),ans[i].end()),ans[i].end());
for(int i = 0;i < cnt;i++)
for(int v : ans[i])
ind[v]++;
}
vector <int> topo()
{
vector <int> res;
queue <int> q;
for(int i = 0;i < cnt;i++)
if(ind[i] == 0)
q.push(i);
while(!q.empty())
{
int u = q.front();
q.pop();
res.push_back(u);
for(int v : ans[u])
{
ind[v]--;
if(ind[v] == 0)
q.push(v);
}
}
return res;
}
};
//ST表
int n,m;
int st[100010][20];
int main()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
st[i][0]=x;
}
int lg=(int)log2(n);
for(int j=1;j<=lg;j++)
for(int i=1;i<=n-(1<<j)+1;i++)
st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
for(int i=1;i<=m;i++)
{
int l,r;
scanf("%d%d",&l,&r);
lg=(int)log2(r-l+1);
printf("%d\n"max(st[l][lg],st[r-(1<<lg)+1][lg]));
}
return 0;
}
//AC机
const int maxn = 2e5 + 5;
const int len = 2e6 + 5;
const int size = 2e5 + 6;
int n;
struct node{
int son[27];
int ans,fail,degree,idx;
void init()
{
memset(son,0,sizeof(son));
ans = fail = idx = 0;
}
}trie[size];
int ans[maxn];
int tot,pidx;
void init()
{
tot = pidx = 0;
trie[0].init();
}
void insert(char s[],int &idx)
{
int u = 0;
for(int i = 1;s[i];i++)
{
int &son = trie[u].son[s[i] - 'a'];
if(!son)
son = ++tot,
trie[son].init();
u = son;
}
if(!trie[u].idx)
trie[u].idx = ++pidx;
idx = trie[u].idx;
}
void build()
{
queue <int> q;
for(int i = 0;i < 26;i++)
if(trie[0].son[i])
q.push(trie[0].son[i]);
while(!q.empty())
{
int u = q.front();
q.pop();
for(int i = 0;i < 26;i++)
{
if(trie[u].son[i])
{
trie[trie[u].son[i]].fail = trie[trie[u].fail].son[i];
trie[trie[trie[u].fail].son[i]].degree++;
q.push(trie[u].son[i]);
}
else
trie[u].son[i] = trie[trie[u].fail].son[i];
}
}
}
void query(char t[])
{
int u = 0;
for(int i = 1;t[i];i++)
u = trie[u].son[t[i] - 'a'],
trie[u].ans++;
}
void topo()
{
queue <int> q;
for(int i = 0;i <= tot;i++)
if(trie[i].degree == 0)
q.push(i);
while(!q.empty())
{
int u = q.front();
q.pop();
ans[trie[u].idx] = trie[u].ans;
int v = trie[u].fail;
trie[v].ans += trie[u].ans;
if(! --trie[v].degree)
q.push(v);
}
}
char s[len];
int idx[maxn];
int main()
{
init();
scanf("%d",&n);
for(int i = 1;i <= n;i++)
{
scanf("%s",s + 1);
insert(s,idx[i]);
ans[i] = 0;
}
build();
scanf("%s",s + 1);
query(s);
topo();
for(int i = 1;i <= n;i++)
printf("%d\n",ans[idx[i]]);
return 0;
}
//线性筛素数
void pre(int n)
{
for(int i = 2;i <= n;i++)
{
if(!np[i])
p.push_back(i);
for(int j : p)
{
if(i * j > n)
break;
np[i * j] = true;
if((i % j) == 0)
break;
}
}
}
//线性求积性函数
vector<int> pri;
bool not_prime[N];
int d[N], num[N];
//(d(n) n因子个数)
void pre(int n)
{
d[1] = 1;
for(int i = 2;i <= n;++i)
{
if (!not_prime[i])
{
pri.push_back(i);
d[i] = 2; // 1, i
num[i] = 1; // i = i ^ 1 num[i*i]=2 num[16]=4 num[28]=2 num[30]=1
}
for(int pri_j : pri)
{
if (i * pri_j > n)
break;
not_prime[i * pri_j] = true;
if (i % pri_j == 0)
{
num[i * pri_j] = num[i] + 1; // gcd(i, pri_j) == pri_j
d[i * pri_j] = d[i] / num[i * pri_j] * (num[i * pri_j] + 1);
// a = i * pri_j
// d[n] = d[prij^num[a]] * d[b]
// d[n] = (num[a] + 1) * d[b] 1
// d[n/prij] = num[a] * d[b] 2
// 1式 除以 2式
// d[n] = d[n/prij] * (num[a] + 1) / num[a]
break;
}
num[i * pri_j] = 1;
d[i * pri_j] = d[i] * 2; // d[pri_j]
}
}
}
//退背包
f[0] = 1;
for(int i = 1;i <= n;i++)
for(int j = m;j >= w[i];j--)
f[j] = (f[j] + f[j - w[i]]) % 10;
for(int i = 1;i <= n;i++)
{
for(int j = 0;j <= m;j++)
g[j] = f[j];
for(int j = w[i];j <= m;j++)
g[j] = (g[j] - g[j - w[i]] + 10) % 10;
for(int j = 1;j <= m;j++)
printf("%d",g[j]);
printf("\n");
}
//主席树
struct seg{
int v,ls,rs;
}t[N << 5];
int cntd,n,m,a[N],root[N];
vector <int> v;
inline int getid(int x)
{
return lower_bound(v.begin(),v.end(),x) - v.begin() + 1;
}
void build(int &rt,int l,int r)
{
rt= ++cntd;
t[rt].v = 0;
if(l == r)
return;
int mid = l + r >> 1;
build(t[rt].ls,l,mid);
build(t[rt].rs,mid + 1,r);
}
inline int clone(int rt)
{
++cntd;
t[cntd] = t[rt];
return cntd;
}
int update(int pos,int rt,int l,int r)
{
rt = clone(rt);
t[rt].v++;
if(l == r)
return rt;
int mid = l + r >> 1;
if(pos <= mid)
t[rt].ls = update(pos,t[rt].ls,l,mid);
else
t[rt].rs = update(pos,t[rt].rs,mid + 1,r);
return rt;
}
int query(int L,int R,int l,int r,int q)
{
if(l == r)
return l;
int mid = l + r >> 1,tmp = t[t[R].ls].v - t[t[L].ls].v;
if(tmp >= q)
return query(t[L].ls,t[R].ls,l,mid,q);
else
return query(t[L].rs,t[R].rs,mid + 1,r,q - tmp);
}
//PAM
int getfail(int x)
{
while(s[pos - len[x] - 1] != s[pos])
x = fail[x];
return x;
}
void insert(char c)
{
int x = c - 'a',p = getfail(last);
if(!nxt[p][x])
{
len[++tot] = len[p] + 2;
fail[tot] = nxt[getfail(fail[p])][x];
nxt[p][x] = tot;
cnt[tot] = cnt[fail[tot]] + 1;
}
last = nxt[p][x];
}
```