zzx_MC_2024

UID: 39323, 注册于 2024-1-11 22:20:00, 最后登录于 2025-3-25 19:16:35, 最后活动于 2025-3-25 19:22:56.

解决了 3 道题目，RP: 17 (No. 2415)

♂

个人简介

AT and Code

-std=c++11 -O2 -Wl,--stack=123456789

代码

剪贴板：

/*
(x-y)(x^2+y^2+xy)
(x-y)((x-y)^2+3xy)
a=x-y,b=xy
a(a^2+3b)
(x-y)^2=x^2+y^2-2xy;
(x+y)^2=x^2+y^2+2xy;
*/

weq是机房J霸！！！

代码模板

【模板】单源最短路径（标准版）

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+114;
int n,m,dis[N],s;
struct node
{
	int x,z;
};
struct nod
{
	int x,z;
};
vector<nod> adj[N];
bool operator <(node x,node y){return x.z>y.z;}
bool flag[N];
void dij()
{
	priority_queue<node> q;
	q.push({s,0});
	memset(flag,0,sizeof flag);
	memset(dis,0x3f,sizeof dis);
	dis[s]=0;
	while(!q.empty())
	{
		node t=q.top();
		q.pop();
		if(flag[t.x])continue;
		flag[t.x]=1;
		for(auto it:adj[t.x])
		{
			if(dis[it.x]>dis[t.x]+it.z)
			{
				dis[it.x]=dis[t.x]+it.z;
				if(!flag[it.x])q.push({it.x,dis[it.x]});
			}
		}
	}
}
int main()
{
//	freopen("P4779_1.in","r",stdin);
//	freopen("P4779__1.out","w",stdout);
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		cin>>x>>y>>z;
		adj[x].push_back({y,z});
	}
	dij();
	for(int i=1;i<=n;i++)cout<<dis[i]<<' ';
	return 0;
}

双hash

#include<bits/stdc++.h>
using namespace std;
#define maxn 1000005
typedef long long ll;
typedef long double ld;

int mod1,base1,power1[maxn],h1[maxn];
int mod2,base2,power2[maxn],h2[maxn];  
int n,m;
char s[maxn];
inline int read()
{
	int x=0,f=1; char ch=getchar();
	for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
	for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*f;
}

void build1()
{
	for (int i=1;i<=n;i++)
		h1[i]=1ll*h1[i-1]*base1%mod1+s[i]-'a';
	power1[0]=1;
	for (int i=1;i<=n;i++)
		power1[i]=1ll*power1[i-1]*base1%mod1;
}
bool check1(int l1,int r1,int l2,int r2)
{
	int len=r1-l1+1;
	int h11=((h1[r1]-1ll*h1[l1-1]*power1[len]%mod1)+mod1)%mod1;
	int h21=((h1[r2]-1ll*h1[l2-1]*power1[len]%mod1)+mod1)%mod1;
	return h11==h21;
}
void build2()
{
	for (int i=1;i<=n;i++)
		h2[i]=1ll*h2[i-1]*base2%mod2+s[i]-'a';
	power2[0]=1;
	for (int i=1;i<=n;i++)
		power2[i]=1ll*power2[i-1]*base2%mod2;
}
bool check2(int l1,int r1,int l2,int r2)
{
	int len=r1-l1+1;
	int h12=((h2[r1]-1ll*h2[l1-1]*power2[len]%mod2)+mod2)%mod2;
	int h22=((h2[r2]-1ll*h2[l2-1]*power2[len]%mod2)+mod2)%mod2;
	return h12==h22;
}

int main()
{
	mod1=998244353,mod2=666623333; base1=233,base2=431;
	scanf("%s",s+1); n=strlen(s+1);
	build1(),build2();
	int id=0;
	for (int T=read();T;T--)
	{
		++id;
		int l1=read(),r1=read(),l2=read(),r2=read();
		if (r1-l1+1!=r2-l2+1)
		{
			puts("No");
			continue;
		}
		puts((check1(l1,r1,l2,r2)&&check2(l1,r1,l2,r2))?"Yes":"No");
	}
	return 0;
}

可持久化线段树（主席树）

#include<bits/stdc++.h>
#define int long long
#define debug(a) cout<<#a<<':'<<a<<endl;
using namespace std;
const int N=100114,M=32;
int n,m,a[N],sum[N*M],lc[N*M],rc[N*M],cnt,b[N],rt[N],p;
void build(int &k,int l,int r)
{
	k=++cnt;
	sum[k]=0;
	if(l==r)return;
	int mid=l+r>>1;
	build(lc[k],l,mid);
	build(rc[k],mid+1,r);
}
int jia(int k,int l,int r)
{
	int xin=++cnt;
	lc[xin]=lc[k],rc[xin]=rc[k],sum[xin]=sum[k]+1;
	if(l==r)return xin;
	int mid=l+r>>1;
	if(p<=mid)lc[xin]=jia(lc[k],l,mid);
	else rc[xin]=jia(rc[k],mid+1,r);
	return xin;
}
int xunwen(int u,int v,int l,int r,int k)
{
	int x=sum[lc[v]]-sum[lc[u]];
	if(l==r)return l;
	int mid=l+r>>1;
	if(k<=x)return xunwen(lc[u],lc[v],l,mid,k);
	else return xunwen(rc[u],rc[v],mid+1,r,k-x);
}
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i],b[i]=a[i];
	sort(b+1,b+1+n);
	int q=unique(b+1,b+1+n)-b-1;
	build(rt[0],1,q);
	for(int i=1;i<=n;i++)
	{
		p=lower_bound(b+1,b+1+q,a[i])-b;
		rt[i]=jia(rt[i-1],1,q);
	}
	while(m--)
	{
		int x,y,z;
		cin>>x>>y>>z;
		cout<<b[xunwen(rt[x-1],rt[y],1,q,z)]<<endl;
	}
	return 0;
}

C(n,m)的求法

暴力

int C(int n,int m)
{
	int ans=1;
	for(int i=n-m+1;i<=n;i++)ans*=i;
	int sum=1;
	for(int i=m;i>=1;i--)sum*=i;
	ans/=sum;
	return ans;
}

优化

int C(int n,int m)
{
	int ans=1;
	int t=n;
	int b=1;
	for(int i=1;i<=m;i++)
	{
		ans=ans*t/b;
		t--;b++;
	}
	return ans;
}

超快速

int qpow(int a,int b,int p)
{
	int res=1;
	while(b)
	{
		if(b&1)
			res=(a*res)%p;
		a*=a;
		a%=p;
		b>>=1;
	}
	return res;
}
void ff()
{
	fac[0]=1;
	for(int i=1;i<=100000;i++)fac[i]=fac[i-1]*i%mod;
}
int C(int n,int m)
{
	return (fac[n]*qpow(fac[n-m],mod-2,mod)%mod*qpow(fac[m],mod-2,mod)%mod)%mod;
}

快速幂

int qpow(int a,int b,int p)
{
	int res=1;
	while(b)
	{
		if(b&1)
			res=(a*res)%p;
		a*=a;
		a%=p;
		b>>=1;
	}
	return res;
}

((qpow(m,n+1,mod)-1+mod)%mod*qpow(m-1,mod-2,mod)%mod-1+mod)%mod//等比数列求和公式

扩欧

扩欧
void ojld(int a,int b)
{
	if(b==0)
	{
		jx=1,jy=0;
		return;
	}
	ojld(b,a%b);
	int tx=jx;
	jx=jy;
	jy=tx-a/b*jy;
}

鼠据生成：

#include<bits/stdc++.h>
using namespace std;
char a[10];
int top;
void ddd(int x)
{
	top=0;
	a[top]='c';
	a[++top]='c';
	string s="";
	while(x)
	{
		s+=(x%10)+'0';
		x/=10;
	}
	reverse(s.begin(),s.end());
	for(int i=0;i<s.size();i++)
	{
		a[++top]=s[i];
	}
	a[++top]='.';
	a[++top]='o';
	a[++top]='u';
	a[++top]='t';
}
int main()
{
	for(int i=1;i<=800;i++)
	{
		freopen("c1.out","r",stdin);
		ddd(i);
		freopen(a,"w",stdout);
		for(int j=1;j<=800;j++)
		{
			int x;
			cin>>x;
			if(i==j)
			{
				cout<<x<<endl;
				break;
			}
		}
		fclose(stdin);
		fclose(stdout);
	}
	return 0;
}

tarjan

//tarjan
#include<bits/stdc++.h>
typedef long long ll;
//#define int long long
using namespace std;
const int N=1e5+114;
int n,m,dfn[N],low[N],tot,ans;
vector<int> adj[N],what[N];
stack<int> st;
int flag[N];
void tarjan(int u)
{
	dfn[u]=low[u]=++tot;
	st.push(u);
	for(auto it : adj[u])
	{
		if(!dfn[it])
		{
			tarjan(it);
			low[u]=min(low[u],low[it]);
		}
		else if(!flag[it])
		{
			low[u]=min(low[u],dfn[it]);
		}
	}
	if(dfn[u]==low[u])
	{
		ans++;
		flag[u]=ans;
		what[ans].push_back(u);
		while(st.top()!=u)
		{
			flag[st.top()]=ans;
			what[ans].push_back(st.top());
			st.pop();
		}
		st.pop();
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		adj[x].push_back(y);
	}
	for(int i=1;i<=n;i++)
	{
		if(!dfn[i])
		{
			tarjan(i);
		}
	}
	int ab=0;
	for(int i=1;i<=ans;i++)
	{
		if(what[i].size()>1)ab++;
	}
    cout<<ab;
	return 0;
}


//求割点
//tarjan
#include<bits/stdc++.h>
typedef long long ll;
#define int long long
using namespace std; //A
const int N=1e5+114;
int n,m,dfn[N],low[N],tot,ans,sbsb,hi;
vector<int> adj[N],what[N];
set<int> anss;
stack<int> st;
int flag[N];
void tarjan(int u,int fa)
{
	dfn[u]=low[u]=++tot;
	st.push(u);int son=0;
	for(auto it : adj[u])
	{
		if(!dfn[it])
		{
			son++;
			tarjan(it,u);
			low[u]=min(low[u],low[it]);
			if(low[it]>=dfn[u] && it!=fa && hi!=u && !(anss.count(u)))
			{
				sbsb++;
				anss.insert(u);
			}
		}
		else
		{
			low[u]=min(low[u],dfn[it]);
		}
	}
	if(hi==u && son>=2)
	{
		sbsb++;
		anss.insert(u);
	}
}
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		adj[x].push_back(y);
		adj[y].push_back(x);
	}
	for(int i=1;i<=n;i++)
	{
		if(!dfn[i])
		{
			hi=i;
			tarjan(i,0);
		}
	}
	cout<<sbsb<<endl;
	for(auto it: anss)
	{
		cout<<it<<' ';
	}
	return 0;
}
//求割边（有重边时）
#include<bits/stdc++.h>
using namespace std;
const int N=30114;
int n,m;
vector<int> adj[N];
int low[N],dfn[N],flag[N],tot,idx;
void tarjan(int u,int fa)
{
	bool sb=0;
	low[u]=dfn[u]=++idx;
	for(auto it:adj[u])
	{
		if(!dfn[it])
		{
			tarjan(it,u);
			low[u]=min(low[u],low[it]);
			if(low[it]>dfn[u])
			{
				tot++;
				flag[it]=1;
			}
		}
		else
		{
			if(it!=fa || sb)
			{
				low[u]=min(low[u],dfn[it]);
			}
			else sb=1;
		}
	}
}
int main()
{
	while(cin>>n>>m && !(n==0 && m==0))
	{
		for(int i=1;i<=m;i++)
		{
			int x,y;
			cin>>x>>y;
			adj[x].push_back(y);
			adj[y].push_back(x);
		}
		tarjan(1,-1);
		cout<<tot<<endl;
		for(int i=1;i<=n;i++)adj[i].clear();
		memset(low,0,sizeof low);
		memset(dfn,0,sizeof dfn);
		tot=0;
	}
	return 0;
}

//边双连通分量（可以用上面的代码改一下）
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
int n,m,dfn[2000010],low[2000010],bel[2000010],ecc;
int shijian;
stack<int> st;
vector<int> adj[4000001];
int head[2000001],ans=1;
struct node
{
	int nxt,v;
}e[4000001];
bool flag[4000001];
int jj;
void add(int x,int y)
{
	e[++ans].v=y;
	e[ans].nxt=head[x];
	head[x]=ans;
}
void tarjan(int u,int edg)
{
	st.push(u);
	dfn[u]=low[u]=++shijian;
	for(int i=head[u];i!=-1;i=e[i].nxt)
	{
		int t=e[i].v;
		if(!dfn[t])
		{
			tarjan(t,i);
			low[u]=min(low[u],low[t]);
			if(low[t]>dfn[u])
			{
				flag[i]=flag[i^1]=1;
			}
		}
		else if(i!=(edg^1))//所以不要走到他的父亲节点去了，解释在下面
		{
			low[u]=min(low[u],dfn[t]);
		}
	}
}
void dfs(int u)
{
	bel[u]=ecc;
	adj[ecc].push_back(u);
	for(int i=head[u];i!=-1;i=e[i].nxt)
	{
		int t=e[i].v;
		if(bel[t] || flag[i])continue;
		dfs(t);
	}
}
int main()
{
	//freopen("name.in","r",stdin);
	//freopen("name.out","w",stdout);
	cin>>n>>m;
	memset(head,-1,sizeof(head));
	for(int i=1;i<=m;i++)
	{
		//✔✘▓※
		int x,y;
		cin>>x>>y;//解释
		add(x,y);//如果ans=3
		add(y,x);//那么这一行执行完后ans=4
		//他们是相对的
	}
	for(int i=1;i<=n;i++)
	{
		if(!dfn[i])tarjan(i,0);
	}
	for(int i=1;i<=n;i++)
	{
		if(!bel[i])
		{
			ecc++;
			dfs(i);
		}
	}
	cout<<ecc<<endl;
	for(int i=1;i<=ecc;i++)
	{
		cout<<adj[i].size();
		for(int j=0;j<adj[i].size();j++)cout<<" "<<adj[i][j];
		cout<<endl;
	}
	return 0;
}

//点双连通分量
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
int n,m,dfn[500010],low[500010],bel[500010],abab;
int shijian;
stack<int> st;
vector<int> ans[1000001];
vector<int> adj[500010];
bool flag[1000001],vis[1000001];
int jj;
void tarjan(int u,int fa)
{
    st.push(u);
    dfn[u]=low[u]=++shijian;
    if(fa==0 && adj[u].size()==0)
    {
        ans[++abab].push_back(u);
        return;
    }
    for(int i=0;i<adj[u].size();i++)
    {
        int t=adj[u][i];
        if(!dfn[t])
        {
            tarjan(t,u);
            low[u]=min(low[u],low[t]);
            if(low[t]>=dfn[u])
            {
                abab++;
                while(st.top()!=t)
                {
                    ans[abab].push_back(st.top());
                    st.pop();
                }
                ans[abab].push_back(t);
                st.pop();
                ans[abab].push_back(u);
            }
        }
        else if(t!=fa)
        {
            low[u]=min(low[u],dfn[t]);
        }
    }
}
int main()
{
    //freopen("name.in","r",stdin);
    //freopen("name.out","w",stdout);
    cin>>n>>m;//K
    for(int i=1;i<=m;i++)
    {
        //✔✘▓※
        int x,y;
        cin>>x>>y;
        if(x == y) continue;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    for(int i=1;i<=n;i++)
    {
        if(!dfn[i])tarjan(i,0);
        while(!st.empty())st.pop();
    }
    cout<<abab<<endl;
    for(int i=1;i<=abab;i++)
    {
        cout<<ans[i].size();
        for(int j=0;j<ans[i].size();j++)cout<<" "<<ans[i][j];
        cout<<endl;
    }
    return 0;
}

树的重心

//树的重心
#include<bits/stdc++.h>
using namespace std;
const int N=20114;
int n;
vector<int> adj[N];
int siz[N],msz[N];
void dfs(int u,int fa)
{
    siz[u]=1;
    for(auto it : adj[u])
    {
        if(it==fa)continue;
        dfs(it,u);
        siz[u]+=siz[it];
        msz[u]=max(msz[u],siz[it]);
    }
    msz[u]=max(msz[u],n-siz[u]);
}
int main()
{
    cin>>n;
    for(int i=1;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    dfs(1,0);
    bool flag=0;
    for(int i=1;i<=n;i++)
    {
        if(msz[i]<=n/2)
        {
            flag=1;
            cout<<i<<endl;
        }
    }
    if(!flag)cout<<"NONE";
    return 0;
}

树状数组

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[1000001],ans,t[1000001],number[1000001];
int lowbit(int x)
{
    return x & -x;
}
void add(int x,int y)
{
    for(;x<=n;x+=lowbit(x))t[x]+=y;
}
int ask(int x)
{
    int sum=0;
    for(;x;x-=lowbit(x))sum+=t[x];
    return sum;
}
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i],a[i]++;
    for(int i=1;i<=n;i++)
    {
        ans+=a[i]-ask(a[i])-1;
        add(a[i],1);
    }
    cout<<ans<<endl;
    for(int i=1;i<n;i++)
    {
        ans-=ask(a[i])-1;
        ans+=n-ask(a[i]);
        cout<<ans<<endl;
    }
    return 0;
}

离散化

#include<bits/stdc++.h>//I
#define inf 0x3f3f3f3f
using namespace std;
int n,b[100001],maxn;
int l[100001],r[100001],g[300001],cnt;
int main()
{
    cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>l[i]>>r[i];g[++cnt]=l[i],g[++cnt]=r[i];
	}
	sort(g+1,g+1+cnt);
	for(int i=1;i<=n;i++)
	{
		int lll=lower_bound(g+1,g+1+cnt,l[i])-g;
		int rrr=lower_bound(g+1,g+1+cnt,r[i])-g;
		b[lll]++;
		b[rrr+1]--;
	}
	int maxnn=0;
	for(int i=1;i<=cnt;i++)b[i]+=b[i-1],maxnn=max(maxnn,b[i]);
	cout<<maxnn<<endl;
    return 0;
}

二维差分

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
int n,k,b[3001][3001],a[3001][3001];
int main()
{
    cin>>n;
	while(n--)
	{
		int l,r,ll,rr;
		cin>>l>>ll>>r>>rr;
		if(ll<l)swap(l,ll);
		if(rr<r)swap(r,rr);
		l++,r++;
		b[l][r]++;
		b[l][rr+1]--;
		b[ll+1][r]--;
		b[ll+1][rr+1]++;
	}
	int c=0;
	for(int i=1;i<=100;i++)
	{
		for(int j=1;j<=100;j++)
		{
			a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+b[i][j];
			if(a[i][j]>=1)c++;
		}
	}
	cout<<c;
    return 0;
}

线段树

//线段树

//我现在的模板
#include<bits/stdc++.h>
#define int long long
#define debug(a) cout<<#a<<':'<<a<<endl;
using namespace std;
const int N=100005;
int n,k,a[N],maxn,minn;
struct
{
	int mx,mn;
}tr[N*4];
void build(int num,int l,int r)
{
	if(l==r)
	{
		tr[num]={a[l],a[r]};
		return;
	}
	int mid=l+r>>1;
	build(num*2,l,mid);
	build(num*2+1,mid+1,r);
	tr[num].mx=max(tr[num*2].mx,tr[num*2+1].mx);
	tr[num].mn=min(tr[num*2].mn,tr[num*2+1].mn);
}
void qunwen(int num,int l,int r,int x,int y)
{
	if(x<=l && r<=y)
	{
		maxn=max(maxn,tr[num].mx);
		minn=min(minn,tr[num].mn);
		return;
	}
	int mid=l+r>>1;
	if(mid>=x)qunwen(num*2,l,mid,x,y);
	if(mid<y)qunwen(num*2+1,mid+1,r,x,y);
}
signed main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)cin>>a[i];
	build(1,1,n);
	for(int i=k;i<=n;i++)
	{
		maxn=-1e9,minn=1e9;
		qunwen(1,1,n,i-k+1,i);
		cout<<maxn<<' '<<minn<<endl;
	}
	return 0;
}
//以前的模板
#include <bits/stdc++.h>
#define lson k << 1
#define rson k << 1 | 1
#define inf 0x3f3f3f3f
using namespace std;

typedef long long ll;
const int maxn = 5e5 + 5;
int a[maxn], n, m;

struct node { // 线段树的结点
	int l,r;
	ll val;
} tree[maxn << 2];

void build(int k, int l, int r) { // 建树
	tree[k].l=l,tree[k].r=r;
	if(l==r)tree[k].val=a[l];
	else
	{
		int mid=l+r>>1;
		build(lson,l,mid);
		build(rson,mid+1,r);
		tree[k].val=tree[lson].val+tree[rson].val;
	}
}

void update(int k, int id, int val) { // a[id] += val
	if(tree[k].l==tree[k].r && tree[k].l==id)
	{
		tree[k].val=a[id]+val;
		a[id]+=val;
		return;
	}
	int mid=tree[k].l+tree[k].r>>1;
	if(id<=mid)update(lson,id,val);
	else update(rson,id,val);
	tree[k].val=tree[lson].val+tree[rson].val;
}

ll query(int k, int l, int r) { // 查询 a[l...r] 的区间和
	int tl=tree[k].l,tr=tree[k].r;
	if(tl>=l && tr<=r)return tree[k].val;
	int mid=tl+tr>>1;
	ll ans=0;
	if(mid>=l)ans=ans+query(lson,l,r);
	if(mid+1<=r)ans=ans+query(rson,l,r);
	return ans;
}

int main() {
	cin>>n>>m;
	for(int i = 1; i <= n; ++i) cin>>a[i];
	// 初始化建树
	build(1,1,n);
	while(m--) {
		int op, x, y;
		cin>>op>>x>>y;
		if(op == 1) {
			update(1, x, y);
		} else {
			cout<<query(1, x, y)<<'\n';
		}
	}
	return 0;
}
//加lazy
#include <bits/stdc++.h>
#define lson k << 1
#define rson k << 1 | 1
using namespace std;

typedef long long ll;
const int maxn = 1e5 + 5;
ll a[maxn], n, m;

struct node {//O
	int l, r;
	ll sum, lazy; // lazy 惰性标记
} tree[maxn << 2];

void build(int k, int l, int r) { // 建树
	tree[k].l=l,tree[k].r=r;
	tree[k].lazy=0;
	if(l==r)tree[k].sum=a[l];
	else
	{
		int mid=l+r>>1;
		build(lson,l,mid);
		build(rson,mid+1,r);
		tree[k].sum=tree[lson].sum+tree[rson].sum;
	}
}

void pushdown(int k) { // 将 k 的 lazy 标记下传
	if(tree[k].lazy)
	{
		tree[lson].sum+=tree[k].lazy*(tree[lson].r-tree[lson].l+1);
		tree[rson].sum+=tree[k].lazy*(tree[rson].r-tree[rson].l+1);
		tree[lson].lazy+=tree[k].lazy;
		tree[rson].lazy+=tree[k].lazy;
		tree[k].lazy=0;
	}
}

void update(int k, int l, int r, int val) { // a[l...r] += val
	int tl=tree[k].l,tr=tree[k].r;
	if(l<=tl && tr<=r)
	{
		tree[k].sum+=val*(tr-tl+1);   //他是一个区间啊
		tree[k].lazy+=val;
		return;
	}
	pushdown(k);
	int mid=tree[k].l+tree[k].r>>1;
	if(mid>=l)update(lson,l,r,val);
	if(mid+1<=r)update(rson,l,r,val);
	tree[k].sum=tree[lson].sum+tree[rson].sum;
} 
ll query(int k, int l, int r) { // 查询 a[l...r] 的和
	int tl=tree[k].l,tr=tree[k].r;
	if(tl>=l && tr<=r)return tree[k].sum;
	pushdown(k);
	int mid=tl+tr>>1;
	ll ans=0;
	if(mid>=l)ans=ans+query(lson,l,r);
	if(mid+1<=r)ans=ans+query(rson,l,r);
	return ans;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0);
	cin>>n>>m;
	for(int i = 1; i <= n; ++i) cin>>a[i];
	build(1, 1, n);
	while(m--) {
		int op, x, y, val;
		cin>>op>>x>>y;
		if(op == 1) {
			cin>>val;
			update(1, x, y, val);
		} else {
			cout<<query(1, x, y)<<'\n';
		}
	}
	return 0;
}

严格次小生成树

//严格次小生成树
#include<bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f3f3f3f
using namespace std;
const int N=1e6+114,M=3e6+114;
int n,m,fa[N];
struct node
{
    int x,z;
};
vector<node> adj[N];
struct nod
{
    int x,y,z;
}edge[M];
bool cmp(nod x,nod y)
{
    return x.z<y.z;
}
int dep[N],tiao[N][51],fir[N][51],sec[N][51];
bool flag[N];
void dfs(int u,int fa,int de)
{
    dep[u]=de;
    for(auto it:adj[u])
    {
        if(it.x==fa)continue;
        tiao[it.x][0]=u;
        fir[it.x][0]=it.z;
        sec[it.x][0]=-inf;
        dfs(it.x,u,de+1);
    }
}
int lca(int xx,int yy)
{
	if(dep[xx]<dep[yy])swap(xx,yy);
	for(int i=50;i>=0;i--)
	{
		if(dep[tiao[xx][i]]>=dep[yy])
		{
			xx=tiao[xx][i];
		}
	}
	if(xx==yy)return xx;
	for(int i=50;i>=0;i--)
	{
		if(tiao[xx][i]!=tiao[yy][i])
		{
			xx=tiao[xx][i];
			yy=tiao[yy][i];
		}
	}
	return tiao[xx][0];
}
int find(int x)
{
    if(fa[x]==x)return fa[x];
    return fa[x]=find(fa[x]);
}
int qunwen(int x,int y,int cost)
{
    int ret=0;
    for(int i=50;i>=0;i--)
    {
        if(dep[tiao[x][i]]>=dep[y])
        {
            if(cost==fir[x][i])ret=max(ret,sec[x][i]);
            else ret=max(ret,fir[x][i]);
            x=tiao[x][i];
        }
    }
    return ret;
}
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        edge[i]={x,y,z};
    }
    sort(edge+1,edge+1+m,cmp);
    int sum=0,ans=0;
    for(int i=1;i<=m;i++)
    {
        int x=edge[i].x,y=edge[i].y;
        int xx=find(x),yy=find(y);
        if(xx==yy)continue;
        adj[x].push_back({y,edge[i].z});
        adj[y].push_back({x,edge[i].z});
        ans++;
        sum+=edge[i].z;
        fa[xx]=yy;
        flag[i]=1;
        if(ans==n-1)break;
    }
    dfs(1,0,0);
	for(int j=1;j<=50;j++)
	{
		for(int i=1;i<=n;i++)
		{
			tiao[i][j]=tiao[tiao[i][j-1]][j-1];
			int temp[4]={fir[i][j-1],sec[i][j-1],fir[tiao[i][j-1]][j-1],sec[tiao[i][j-1]][j-1]};
			sort(temp,temp+4);
			fir[i][j]=temp[3];
			sec[i][j]=temp[2];
			if(fir[i][j]==sec[i][j])sec[i][j]=temp[1];
		}
	}
    ans=inf;
    for(int i=1;i<=m;i++)
    {
        if(!flag[i])
        {
            int x=edge[i].x;
            int y=edge[i].y;
            int lcaa=lca(x,y);
            int tttt=max(qunwen(x,lcaa,edge[i].z),qunwen(y,lcaa,edge[i].z));
            ans=min(ans,sum+edge[i].z-tttt);
        }
    }
    cout<<ans;
    return 0;
}

CSP-S2019树的重心



CSP2019树的重心
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e5+114;
int T,son[N][2],siz[N],tiao[N][31],ans;
vector<int> adj[N];
int n;
void rrr(int u)
{
	tiao[u][0]=son[u][0];
	for(int i=1;i<=20;i++)
	{
		tiao[u][i]=tiao[tiao[u][i-1]][i-1];
	}
}
void dfs(int u,int fa)
{
	siz[u]=1;
	for(auto it: adj[u])
	{
		if(it==fa)continue;
		dfs(it,u);
		siz[u]+=siz[it];
		if(siz[it]>siz[son[u][0]])
		{
			son[u][1]=son[u][0];
			son[u][0]=it;
		}
		else if(siz[it]>siz[son[u][1]])
			son[u][1]=it;
	}
	rrr(u);
}
void find(int u)
{
	int t=u;
	for(int i=20;i>=0;i--)
	{
		if(siz[tiao[u][i]]>siz[t]/2)
			u=tiao[u][i];
	}
	ans+=u;
	if(siz[t]%2==0)
	{
		u=tiao[u][0];
		if(2*siz[u]==siz[t])
		{
			ans+=u;
		}
	}
}
void run(int u,int fa)
{
	int t1=son[u][0],t2=siz[u];
	for(auto v:adj[u])
	{
		if(v==fa)continue;
		if(v==t1)
		{
			son[u][0]=siz[son[u][1]]>n-t2?son[u][1]:fa;
		}
		else son[u][0]=siz[t1]>n-t2?t1:fa;
		siz[u]=n-siz[v];
		rrr(u);
		find(u);
		find(v);
		run(v,u);
	}
	son[u][0]=t1;
	siz[u]=t2;
	rrr(u);
}
signed main()
{
	cin>>T;
	while(T--)
	{
		memset(son,0,sizeof son);
		memset(siz,0,sizeof siz);
		memset(tiao,0,sizeof tiao);
		ans=0;
		cin>>n;
		for(int i=1;i<n;i++)
		{
			int x,y;
			cin>>x>>y;
			adj[x].push_back(y);
			adj[y].push_back(x);
		}
		dfs(1,0);
		run(1,0);
		cout<<ans<<endl;
		for(int i=1;i<=n;i++)adj[i].clear();
	}
	return 0;
}

树链剖分

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,root;
const int N=500005;
vector<int> adj[N];
int dep[N],fa[N],son[N],top[N],siz[N];
void dfs1(int x)
{
	siz[x]=1;
	for(auto it:adj[x])
	{
		if(it==fa[x])continue;
		fa[it]=x;
		dep[it]=dep[x]+1;
		dfs1(it);
		if(siz[son[x]]<siz[it])son[x]=it;
		siz[x]+=siz[it];
	}
}
void dfs2(int x)
{
	if(!son[x])return;
	top[son[x]]=top[x];
	dfs2(son[x]);
	for(auto it:adj[x])
	{
		if(fa[x]==it || it==son[x])continue;
		top[it]=it;
		dfs2(it);
	}
}
int lca(int x,int y)
{
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		x=fa[top[x]];
	}
	return dep[x]<dep[y]?x:y;
}
signed main()
{
	cin>>n>>m>>root;
	for(int i=1;i<n;i++)
	{
		int x,y;
		cin>>x>>y;
		adj[x].push_back(y);
		adj[y].push_back(x);
	}
	dep[root]=1;
	dfs1(root);
	top[root]=root;
	dfs2(root);
	while(m--)
	{
		int x,y;
		cin>>x>>y;
		printf("%d\n",lca(x,y));
	}
	return 0;
}

同余最短路&&跳楼机

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+114;
int h,x,y,z,dis[N],s;
struct node
{
	int x,z;
};
struct nod
{
	int x,z;
};
vector<nod> adj[N];
bool operator <(node x,node y){return x.z>y.z;}
bool flag[N];
void dij()
{
	priority_queue<node> q;
	q.push({s,0});
	memset(flag,0,sizeof flag);
	memset(dis,0x3f,sizeof dis);
	dis[s]=0;
	while(!q.empty())
	{
		node t=q.top();
		q.pop();
		if(flag[t.x])continue;
		flag[t.x]=1;
		for(auto it:adj[t.x])
		{
			if(dis[it.x]>dis[t.x]+it.z)
			{
				dis[it.x]=dis[t.x]+it.z;
				if(!flag[it.x])q.push({it.x,dis[it.x]});
			}
		}
	}
}
signed main()
{
	cin>>h>>x>>y>>z;
	if(x==1 || y==1 || z==1)
	{
		cout<<h<<endl;
		return 0;
	}
	h--;
	for(int i=0;i<x;i++)
	{
		adj[i].push_back({(i+y)%x,y});
		adj[i].push_back({(i+z)%x,z});
	}
	s=0;
	dij();
	int sum=0;
	for(int i=0;i<=x-1;i++)
		if(h>=dis[i])sum+=(h-dis[i])/x+1;
	cout<<sum<<endl;
	return 0;
}
//不开long long见祖宗

圆方树

#include<bits/stdc++.h>
using namespace std;
const int N=2000001,M=700001;
int n,m,dfn[M],low[M],abab;
int shijian;
stack<int> st;
vector<int> ans[N];
vector<int> adj[M];
int top[N],son[N],dep[N],siz[N],fa[N];
void add_ans(int u,int v)
{
	ans[u].push_back(v);
	ans[v].push_back(u);
}
void tarjan(int u)
{
	st.push(u);
	dfn[u]=low[u]=++shijian;
	for(int i=0;i<adj[u].size();i++)
	{
		int t=adj[u][i];
		if(!dfn[t])
		{
			tarjan(t);
			low[u]=min(low[u],low[t]);
			if(low[t]==dfn[u])
			{
				abab++;
				add_ans(u,abab);
				while(st.top()!=t)
				{
					add_ans(st.top(),abab);
					st.pop();
				}
				add_ans(t,abab);
				st.pop();
			}
		}
		else
			low[u]=min(low[u],dfn[t]);
	}
}
void dfs1(int u,int f)
{
	dep[u]=dep[f]+1;
	fa[u]=f;
	siz[u]=1;
	for(auto v:ans[u])
	{
		if(v==f)continue;
		dfs1(v,u);
		siz[u]+=siz[v];
		if(siz[son[u]]<siz[v])son[u]=v;
 	}
}
void dfs2(int u,int tp)
{
	top[u]=tp;
	if(!son[u])return;
	dfs2(son[u],tp);
	for(auto v:ans[u])
		if(v!=fa[u] && v!=son[u])
			dfs2(v,v);
}
int lca(int x,int y)
{
	while (top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		x=fa[top[x]];
	}
	if(dep[x]<dep[y])return x;
	return y;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
//	freopen("P4320_2.in","r",stdin);
//	freopen("ssssssssssss.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		adj[x].push_back(y);
		adj[y].push_back(x);
	}
	abab=n;
	tarjan(1);
	dfs1(1,0);
	dfs2(1,1);
	int q;
	cin>>q;
	while(q--)
	{
		int x,y;
		cin>>x>>y;
		cout<<((dep[x]+dep[y]-dep[lca(x,y)]*2)>>1)+1<<endl;
	}
	return 0;
}
/*
5 5
1 2
1 3
1 4
3 4
4 5
1
4 3
*/

支配树

没环

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=65540;
int n,in[N],dep[N];//拓扑序
vector<int> adj[N],fan[N],shu[N];
int tiao[N][25],siz[N];
int lca(int x,int y)
{
	if(dep[x]<dep[y])swap(x,y);
	for(int i=20;i>=0;i--)
	{
		if(dep[tiao[x][i]]>=dep[y])
		{
			x=tiao[x][i];
		}
	}
	if(x==y)
		return x;
	for(int i=20;i>=0;i--)
	{
		if(tiao[x][i]!=tiao[y][i])
		{
			x=tiao[x][i];
			y=tiao[y][i];
		}
	}
	return tiao[x][0];
}
void topu112(int s)
{
	queue<int> q;
	q.push(s);
	while(!q.empty())
	{
		int t=q.front();
		q.pop();
		for(auto it:adj[t])
		{
			if(fan[it].size()<2 && !tiao[it][0])
			{
				shu[t].push_back(it);
				tiao[it][0]=t;
				for(int i=1;i<=20;i++)
				{
					tiao[it][i]=tiao[tiao[it][i-1]][i-1];
				}
				dep[it]=dep[t]+1;
			}
			else if(!tiao[it][0])
			{
				int t=fan[it][0],tt=fan[it][1];
				int anss=lca(t,tt);
				for(int i=2;i<fan[it].size();i++)
				{
					anss=lca(anss,fan[it][i]);
				}
				shu[anss].push_back(it);
				tiao[it][0]=anss;
				for(int i=1;i<=20;i++)
				{
					tiao[it][i]=tiao[tiao[it][i-1]][i-1];
				}
				dep[it]=dep[anss]+1;
			}
			in[it]--;
			if(!in[it])q.push(it);
		}
	}
}
void dfs(int u)
{
	siz[u]=1;
	for(auto it:shu[u])
	{
		dfs(it);
		siz[u]+=siz[it];
	}
}
signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int ssss;
		cin>>ssss;
		while(ssss!=0)
		{
			adj[ssss].push_back(i);
			fan[i].push_back(ssss);
			in[i]++;
			cin>>ssss;
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(!in[i])
		{
			adj[0].push_back(i);
			fan[i].push_back(0);
			in[i]++;
		}
	}
	topu112(0);
	dfs(0);
	for(int i=1;i<=n;i++)
	{
		cout<<siz[i]-1<<endl;
	}
	return 0;
}

LCA

int lca(int x,int y)
{
	if(dep[x]<dep[y])swap(x,y);
	for(int i=20;i>=0;i--)
	{
		if(dep[tiao[x][i]]>=dep[y])
		{
			x=tiao[x][i];
		}
	}
	if(x==y)
		return x;
	for(int i=20;i>=0;i--)
	{
		if(tiao[x][i]!=tiao[y][i])
		{
			x=tiao[x][i];
			y=tiao[y][i];
		}
	}
	return tiao[x][0];
}

二叉树前、中、后序遍历：

#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> adj[1000001];
void xian(int x)
{
    cout<<x<<' ';
    if(adj[x][0]!=0)xian(adj[x][0]);
    if(adj[x][1]!=0)xian(adj[x][1]);
}
void zhong(int x)
{
    if(adj[x][0]!=0)zhong(adj[x][0]);
    cout<<x<<' ';
    if(adj[x][1]!=0)zhong(adj[x][1]);
}
void hou(int x)
{
    if(adj[x][0]!=0)hou(adj[x][0]);
    if(adj[x][1]!=0)hou(adj[x][1]);
    cout<<x<<' ';
}
int main()
{
    // freopen("filename.in", "r", stdin);
    // freopen("filename.out", "w", stdout);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x,y;
        cin>>x>>y;
        adj[i].push_back(x);
        adj[i].push_back(y);
    }
    xian(1);
    cout<<endl;
    zhong(1);
    cout<<endl;
    hou(1);
    cout<<endl;
    return 0;
}

dij:

struct nod
{
	int x,z;
};
bool operator <(nod xx,nod yy)
{
	return xx.z>yy.z;
}
vector<nod> adj[200100];
int dis[1000001];
bool flag[1000001];
void sb(int s)
{
	priority_queue<nod> q;
	q.push({s,0});
	memset(dis,0x7f,sizeof(dis));
	dis[s]=0;
	while(!q.empty())
	{
		nod t=q.top();
		q.pop();
	//	cout<<t.x<<endl;
		if(flag[t.x])
			continue;
		flag[t.x]=true;
		for(int i=0;i<adj[t.x].size();i++)
		{
			nod tt=adj[t.x][i];
			if(!flag[tt.x]&&dis[tt.x]>t.z+tt.z)
			{
				dis[tt.x]=t.z+tt.z;
				q.push({tt.x,dis[tt.x]});
			}
		}
	}
}

floyd:

for(int k=1;k<=n;k++)
{
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(i!=j && j!=k && i!=k)
			{
				c[i][j]=min(c[i][j],c[i][k]+c[k][j]);
			}
		}
	}
}

快读：

inline int read(){int 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<<3)+(x<<1)+(ch^48),ch=getchar();return x*f;}

线性筛

void init(int n){
	memset(v,0,sizeof(v));
	int tot=0;
	for(int i=2;i<=n;i++){
		if(!v[i]){
			p[++tot]=i;
		}
		for(int k=1;k<=tot;k++){
			if(i*p[k]>n)
				break;
			v[i*p[k]]=1;
			if(i%p[k]==0)
				break;
		}
	}
}

通过的题目
H1000
bzoj#P2885
bzoj#P4429
最近活动
- 华为算法精英实战营第六期（HydroOJ 镜像测试赛） IOI
最近编写的题解

This person is lazy and didn't write any solutions.
Stat
Rating

系统测试: 1

zzx_MC_2024

个人简介

代码模板

【模板】单源最短路径（标准版）

双hash

可持久化线段树（主席树）

C(n,m)的求法

暴力

优化

超快速

快速幂

扩欧

鼠据生成：

tarjan

树的重心

树状数组

离散化

二维差分

线段树

严格次小生成树

CSP-S2019树的重心

树链剖分

同余最短路&&跳楼机

圆方树

支配树

没环

LCA

二叉树前、中、后序遍历：

dij:

floyd:

快读：

线性筛

通过的题目

最近活动

最近编写的题解

Stat

Rating

题目标签

状态

开发

支持

还没有账户？

登录