• 个人简介

    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;
    		}
    	}
    }
    
    
  • 通过的题目

  • 最近活动

  • 最近编写的题解

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

  • Rating

题目标签

系统测试
1