Lvat_s Blog

首先树同构我是写过的……就是BJOI那题

然后图同构我是不会的……

然后就花了点头盾看了题解。

原来和树Hash差不多，只要进行迭代就好了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int M=4005,N=205;
const long long P1=808080808080803ll,P2=888888888888887ll;

int n,m,hA[N],hB[N],enA,enB,test;
long long valA_1[N],valB_1[N],valA_2[N],valB_2[N],tmp1[N],tmp2[N],Vt1[N],Vt2[N];

struct Edge{
int b,next;
}eA[M<<1],eB[M<<1];

void AddEdgeA(int sa,int sb){
eA[++enA].b=sb;
eA[enA].next=hA[sa];
hA[sa]=enA;
}

void AddEdgeB(int sa,int sb){
eB[++enB].b=sb;
eB[enB].next=hB[sa];
hB[sa]=enB;
}

void Solve_A(){
for(int i=1;i<=n;i++){
	int cnt=0;
	for(int j=hA[i];j;j=eA[j].next){
		int v=eA[j].b;cnt++;
		tmp1[cnt]=valA_1[v];
		tmp2[cnt]=valA_2[v];
	}
	sort(tmp1+1,tmp1+cnt+1);
	sort(tmp2+1,tmp2+cnt+1);
	long long Ha1=0,Ha2=0;
    for(int j=1;j<=cnt;j++){Ha1=(Ha1*233ll+tmp1[j])%P1;Ha2=(Ha2*666ll+tmp2[j])%P2;}
    Vt1[i]=Ha1;Vt2[i]=Ha2;
}
for(int i=1;i<=n;i++){valA_1[i]=Vt1[i];valA_2[i]=Vt2[i];}
}

void Solve_B(){
for(int i=1;i<=n;i++){
	int cnt=0;
	for(int j=hB[i];j;j=eB[j].next){
		int v=eB[j].b;cnt++;
		tmp1[cnt]=valB_1[v];
		tmp2[cnt]=valB_2[v];
	}
	sort(tmp1+1,tmp1+cnt+1);
	sort(tmp2+1,tmp2+cnt+1);
	long long Ha1=0,Ha2=0;
    for(int j=1;j<=cnt;j++){Ha1=(Ha1*233ll+tmp1[j])%P1;Ha2=(Ha2*666ll+tmp2[j])%P2;}
    Vt1[i]=Ha1;Vt2[i]=Ha2;
}
for(int i=1;i<=n;i++){valB_1[i]=Vt1[i];valB_2[i]=Vt2[i];}
}

void Solve(){
scanf("%d %d",&n,&m);
memset(hA,0,sizeof(hA));
memset(hB,0,sizeof(hB));
enA=0;enB=0;
for(int i=1;i<=m;i++){
	int u,v;
	scanf("%d %d",&u,&v);
	AddEdgeA(u,v);AddEdgeA(v,u);
}
for(int i=1;i<=m;i++){
	int u,v;
	scanf("%d %d",&u,&v);
	AddEdgeB(u,v);AddEdgeB(v,u);
}
for(int i=1;i<=n;i++)valA_1[i]=valA_2[i]=valB_1[i]=valB_2[i]=1;
for(int i=1;i<=n;i++)Solve_A();
for(int i=1;i<=n;i++)Solve_B();
sort(valA_1+1,valA_1+n+1);
sort(valA_2+1,valA_2+n+1);
sort(valB_1+1,valB_1+n+1);
sort(valB_2+1,valB_2+n+1);
int flag=1;
for(int i=1;i<=n;i++)if(valA_1[i]!=valB_1[i] || valA_2[i]!=valB_2[i]){puts("NO");flag=0;break;}
if(flag)puts("YES");
}

int main(){
freopen("1676.in","r",stdin);
freopen("1676.out","w",stdout);
scanf("%d",&test);
while(test--)Solve();
return 0;
}

维护相等的关系要用并查集

而对于不等关系，因为没有传递性我们用一个set来维护

合并时根据set的大小启发式合并就好了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<set>
using namespace std;

const int N=200005;

int n,f[N],b[N],cnt,id[N];
set<int> S[N];

struct Save{
int a,b,p;
}sav[N];

int Find(int x){return f[x]==x?x:f[x]=Find(f[x]);}

void Union(int x,int y){
if(x==y)return;
if(S[x].size()>S[y].size())swap(x,y);
for(set<int>::iterator i=S[x].begin();i!=S[x].end();i++)S[y].insert(Find(*i));
f[x]=y;
}

int main(){
freopen("1515.in","r",stdin);
freopen("1515.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){
    scanf("%d %d %d",&sav[i].a,&sav[i].b,&sav[i].p);
    b[++cnt]=sav[i].a;f[cnt]=cnt;
    b[++cnt]=sav[i].b;f[cnt]=cnt;
}
sort(b+1,b+cnt+1);
cnt=unique(b+1,b+cnt+1)-b-1;
for(int i=1;i<=n;i++){
	sav[i].a=Find(lower_bound(b+1,b+cnt+1,sav[i].a)-b);
	sav[i].b=Find(lower_bound(b+1,b+cnt+1,sav[i].b)-b);
	if(sav[i].p){
		if(S[sav[i].b].find(sav[i].a)!=S[sav[i].b].end() || S[sav[i].a].find(sav[i].b)!=S[sav[i].a].end())puts("NO");
		else puts("YES"),Union(sav[i].a,sav[i].b);
	}
	else {
		if(sav[i].a==sav[i].b)puts("NO");
		else puts("YES"),S[sav[i].a].insert(sav[i].b),S[sav[i].b].insert(sav[i].a);
	}
}
return 0;
}

首先最大值最小显然是二分

然后就是混合图的欧拉回路

首先我们对于无向图的欧拉回路可以记录点的度数(度数为偶数)，有向图的欧拉回路则是Abs(入度-出度)为偶数时有欧拉回路

那么混合图怎么办？网络流判定就好了。

为了方便和卡常数我所有的流量都除以了2.

我们把无向边随便定个方向再计算出度和入度，然后再连接一条反向边流量为1表示可以返回(因为可能无向边定的方向是相反的，那么对入度和出度会造成总共2的影响，所以连接流量为1)

然后对于入度>出度的点，我们连接源点到这个点，流量是入度减去出度再除以2.

否则连接这个点到汇点，流量是出度减去入度再除以2.

那么判断这个图是否满流就知道能不能形成欧拉回路了(因为欧拉回路每条边都经过所以一定满流)

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;

const int N=2005,INF=2100000000;

int n,m,h[N],level[N],S,T,cur[N],in[N],out[N],en;
queue<int> Q;

struct E{
int u,v,a,b;
}es[N];

struct Edge{
int b,f,back,next;
}e[N<<2];

int Abs(int x){return x>0?x:-x;}

void AddEdge(int sa,int sb,int sc){
e[++en].b=sb;
e[en].f=sc;
e[en].back=en+1;
e[en].next=h[sa];
h[sa]=en;
swap(sa,sb);
e[++en].b=sb;
e[en].f=0;
e[en].back=en-1;
e[en].next=h[sa];
h[sa]=en;
}

int BFS(){
memset(level,0,sizeof(level));
Q.push(S);
level[S]=1;
while(!Q.empty()){
    int u=Q.front();
    Q.pop();
    for(int i=h[u];i;i=e[i].next){
        int v=e[i].b;
        if(level[v] || !e[i].f)continue;
        level[v]=level[u]+1;
        Q.push(v);
    }
}
return level[T];
}

int DFS(int u,int flow){
if(u==T)return flow;
int f=flow;
for(int &i=cur[u];i;i=e[i].next){
    int v=e[i].b,fl;
    if(level[v]==level[u]+1 && e[i].f && (fl=DFS(v,min(f,e[i].f)))){
		f-=fl;
		e[i].f-=fl;
		e[e[i].back].f+=fl;
		if(f==0)return flow;
    }
}
return flow-f;
}

int Dinic(){
int ans=0;
while(BFS()){for(int i=1;i<=n+2;i++)cur[i]=h[i];ans+=DFS(S,INF);}
return ans;
}

bool Odd(){for(int i=1;i<=n;i++)if(Abs(in[i]-out[i])&1)return 1;return 0;}

bool Test(int k){
memset(in,0,sizeof(in));
memset(out,0,sizeof(out));
memset(h,0,sizeof(h));
en=0;S=n+1;T=n+2;
for(int i=1;i<=m;i++){
	if(es[i].a<=k && es[i].b<=k)AddEdge(es[i].v,es[i].u,1),out[es[i].u]++,in[es[i].v]++;
	else if(es[i].a<=k)out[es[i].u]++,in[es[i].v]++;
	else if(es[i].b<=k)out[es[i].v]++,in[es[i].u]++;
	else return 0;
}
if(Odd())return 0;
int ank=0;
for(int i=1;i<=n;i++){
	if(in[i]>out[i])AddEdge(S,i,in[i]-out[i]>>1),ank+=in[i]-out[i]>>1;
    if(in[i]<out[i])AddEdge(i,T,out[i]-in[i]>>1);
}
return Dinic()==ank;
}

int main(){
freopen("2095.in","r",stdin);
freopen("2095.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++)scanf("%d %d %d %d",&es[i].u,&es[i].v,&es[i].a,&es[i].b);
int l=1,r=1000,ans=0;
while(l<=r){
    int mid=l+r>>1;
    if(Test(mid))r=mid-1,ans=mid;
    else l=mid+1;
}
if(!ans)puts("NIE");
else printf("%d\n",ans);
return 0;
}

这题一眼FFT，注意$a_i$的范围也是10W左右(题目没写)

怎么做：构建指数型母函数$F(x)=a_0+a_1*x+...+a_k*x^k$，其中$a_i$是长度为$i$的木棍个数，指数就是长度

那么卷积一次后顺着扫描一遍，边扫描边统计当前有多少种组合情况，注意偶数会多算一倍需要减掉

那么不能组成的概率就是当前的组合种数乘以当前长度的木棍数

最后答案只需要用1减一下就好了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
 
const int N=262144;
const double Pi=acos(-1);
 
int n,Step,Rev[N],tn,test,nn,Su[N];
 
struct Complex{
double a,b;
Complex(){}
Complex(double sa,double sb){a=sa;b=sb;}
friend Complex operator+(Complex A,Complex B){return Complex(A.a+B.a,A.b+B.b);}
friend Complex operator-(Complex A,Complex B){return Complex(A.a-B.a,A.b-B.b);}
friend Complex operator*(Complex A,Complex B){return Complex(A.a*B.a-A.b*B.b,A.b*B.a+B.b*A.a);}
}A[N];
 
void FFT(Complex *r,int flag){
for(int i=0;i<n;i++)if(i<Rev[i])swap(r[i],r[Rev[i]]);
for(int k=1;k<n;k<<=1){
    Complex wk=Complex(cos(Pi/k),flag*sin(Pi/k));
    for(int i=0;i<n;i+=k<<1){
        Complex wkj=Complex(1.0,0.0);
        for(int j=0;j<k;j++){
            Complex x=r[i+j],y=r[i+j+k]*wkj;
            r[i+j]=x+y;
            r[i+j+k]=x-y;
            wkj=wkj*wk;
        }
    }
}
if(flag==-1)for(int i=0;i<n;i++)r[i].a/=n;
}
 
int main(){
freopen("3513.in","r",stdin);
freopen("3513.out","w",stdout);
scanf("%d",&test);
while(test--){
    scanf("%d",&tn);nn=0;Rev[0]=0;
    memset(Su,0,sizeof(Su));
    for(int i=1;i<=tn;i++){int x;scanf("%d",&x);Su[x]++;nn=max(x,nn);}
    nn++;
    nn<<=1;
    for(n=1,Step=0;n<nn;n<<=1,Step++);
    nn>>=1;
    for(int i=0;i<n;i++)Rev[i]=(Rev[i>>1]>>1)|((i&1)<<(Step-1));
    for(int i=0;i<n;i++)A[i]=Complex(Su[i],0.0);
    FFT(A,1);
    for(int i=0;i<n;i++)A[i]=A[i]*A[i];
    FFT(A,-1);
    long long ans=0,tot=1ll*tn*(tn-1)*(tn-2)/6,can=0;
    for(int i=0;i<=nn;i++){
        can+=(long long)(A[i].a+0.5);
        if(!(i%2))can-=Su[i/2];
        if(!Su[i])continue;
        ans+=Su[i]*can;
    }
    ans>>=1;
    printf("%.7lf\n",1.0-1.0*ans/tot);
}
return 0;
}

首先你会发现这是一个最短路

然后你会发现边数太多了

然后就不会了

hzwer教导我们：不连边也能跑最短路

具体就是设定一个高度不断下降，像分层图那么搞就可以了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
 
const int N=155,INF=1000000000,dx[]={1,-1,0,0,0},dy[]={0,0,-1,1,0};
 
int n,m,A[N][N],B[N][N],X[5],Y[5],D[N][N][N<<1],ans=INF,flag,num,a1,a2,b1,b2,c1,c2;
bool vis[N][N][N<<1];
 
struct Data{
int v,x,y,s;
Data(int vs,int xs,int ys,int ss){v=vs;x=xs;y=ys;s=ss;}
friend bool operator<(Data A,Data B){return A.v>B.v;}
};
 
priority_queue<Data> PQ;
 
void Dijkstra(int Xs,int Ys){
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        for(int k=0;k<=num;k++){
            D[i][j][k]=INF;
            vis[i][j][k]=0;
        }
    }
}
D[Xs][Ys][B[Xs][Ys]]=A[Xs][Ys];
while(!PQ.empty())PQ.pop();
vis[Xs][Ys][0]=1;
PQ.push(Data(A[Xs][Ys],Xs,Ys,B[Xs][Ys]));
while(!PQ.empty() && !(vis[X[1]][Y[1]][0] && vis[X[2]][Y[2]][0] && vis[X[3]][Y[3]][0])){
    Data u=PQ.top();PQ.pop();
    if(vis[u.x][u.y][u.s])continue;
    vis[u.x][u.y][u.s]=1;
    if(u.s){
        for(int i=0;i<5;i++){
            int nx=u.x+dx[i],ny=u.y+dy[i];
            if(nx<1 || nx>n || ny<1 || ny>m || vis[nx][ny][u.s-1])continue;
            if(u.v<D[nx][ny][u.s-1]){
                D[nx][ny][u.s-1]=u.v;
                PQ.push(Data(u.v,nx,ny,u.s-1));
            }
        }
    }
    else {
        if(D[u.x][u.y][B[u.x][u.y]]>u.v+A[u.x][u.y]){
            D[u.x][u.y][B[u.x][u.y]]=u.v+A[u.x][u.y];
            PQ.push(Data(D[u.x][u.y][B[u.x][u.y]],u.x,u.y,B[u.x][u.y]));
        }
    }
}
}
 
int main(){
freopen("2143.in","r",stdin);
freopen("2143.out","w",stdout);
scanf("%d %d",&n,&m);num=n+m-2;
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++)scanf("%d",&B[i][j]),B[i][j]=min(B[i][j],max(num-i-j,i+j-2));
}
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++)scanf("%d",&A[i][j]);
}
for(int i=1;i<=3;i++)scanf("%d %d",&X[i],&Y[i]);
Dijkstra(X[1],Y[1]);a1=D[X[2]][Y[2]][0];a2=D[X[3]][Y[3]][0];
Dijkstra(X[2],Y[2]);b1=D[X[1]][Y[1]][0];b2=D[X[3]][Y[3]][0];
Dijkstra(X[3],Y[3]);c1=D[X[1]][Y[1]][0];c2=D[X[2]][Y[2]][0];
if(ans>b1+c1)ans=b1+c1,flag=0;
if(ans>a1+c2)ans=a1+c2,flag=1;
if(ans>a2+b2)ans=a2+b2,flag=2;
if(ans==INF)puts("NO");
else {printf("%c\n%d\n",'X'+flag,ans);}
return 0;
}

dfs判定一下就没了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
 
const int N=20005;
const long double eps=1e-8;
 
int t,n,m,h[N],vis[N],en,flag;
long double dep[N];
bool d[N];
 
struct Edge{
int b,next;
long double l1,l2;
bool l;
}e[N];
 
void AddEdge(int sa,int sb,int sc,int sd,bool se){
e[++en].b=sb;
e[en].l1=sc;
e[en].l2=sd;
e[en].l=se;
e[en].next=h[sa];
h[sa]=en;
}
 
void DFS(int u,int fa){
vis[u]=1;
for(int i=h[u];i && !flag;i=e[i].next){
    int v=e[i].b;
    if(v==fa)continue;
    if(!vis[v]){
        d[v]=(d[u]^e[i].l);
        dep[v]=dep[u]+log(e[i].l2)-log(e[i].l1);
        DFS(v,u);
    }
    else {
        if(d[v]!=(d[u]^e[i].l) || fabs(dep[u]-dep[v]+log(e[i].l2)-log(e[i].l1))>eps){flag=1;return;}
    }
}
}
 
int main(){
freopen("4602.in","r",stdin);
freopen("4602.out","w",stdout);
scanf("%d",&t);
for(int i=1;i<=t;i++){
    scanf("%d %d",&n,&m);
    memset(vis,0,sizeof(vis));
    memset(h,0,sizeof(h));
    en=flag=0;
    for(int j=1;j<=m;j++){
        int u,v,x,y;
        scanf("%d %d %d %d",&u,&v,&x,&y);
        if(y<0){AddEdge(u,v,x,-y,1);AddEdge(v,u,-y,x,1);}
        else {AddEdge(u,v,x,y,0);AddEdge(v,u,y,x,0);}
    }
    for(int j=1;j<=n && !flag;j++)if(!vis[j]){dep[j]=0;DFS(j,j);}
    printf("Case #%d: %s\n",i,flag?"No":"Yes");
}
return 0;
}

Lucas定理的运用

$C(n,k)=C(n/Mod,k/Mod)*C(n\%Mod,k\%Mod)$

那么我们发现因为是求$C(n,0)+C(n,1)+...+C(n,k)$，对于其中的$C(n\%Mod,i)$,$0<=i<=k\%Mod$似乎会用很多次

然后推一下式子就发现这个可以处理成一个前缀和

然后就没了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
 
const int Mod=2333;
 
int t,C[Mod][Mod],Sum[Mod][Mod];
long long n,k;
 
void Pre(){
C[0][0]=1;
for(int i=1;i<Mod;i++){
    C[i][0]=C[i][i]=1;
    for(int j=1;j<i;j++){C[i][j]=C[i-1][j]+C[i-1][j-1];if(C[i][j]>=Mod)C[i][j]-=Mod;}
}
for(int i=0;i<Mod;i++)Sum[0][i]=1;
for(int i=1;i<Mod;i++){
    Sum[i][0]=1;
    for(int j=1;j<Mod;j++){Sum[i][j]=Sum[i][j-1]+C[i][j];if(Sum[i][j]>=Mod)Sum[i][j]-=Mod;}
}
}
 
int Lucas(long long n,long long k){return k==0?1:C[n%Mod][k%Mod]*Lucas(n/Mod,k/Mod)%Mod;}
 
int Cal(long long n,long long k){
if(k<0)return 0;
if(n<Mod)return Sum[n][k];
return (Lucas(n/Mod,k/Mod)*Sum[n%Mod][k%Mod]+Cal(n/Mod,k/Mod-1)*Sum[n%Mod][Mod-1])%Mod;
}
 
int main(){
freopen("4591.in","r",stdin);
freopen("4591.out","w",stdout);
scanf("%d",&t);
Pre();
while(t--){
    scanf("%lld %lld",&n,&k);
    printf("%d\n",Cal(n,k));
}
return 0;
}

首先这题显然是线段树

0操作 区间直接赋值为0 很简单

2操作 统计最长连续0的个数 记录lx,rx,mx三个量，随便合并一下就行了，很简单

1操作……

首先需要记录一个sum表示当前区间有多少脑组织

然后二分填满的位置，我偷懒写了线段树外面的二分，然后时间复杂度就多了一个log

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
 
const int N=200005;
 
int n,m;
 
struct SegTree{
int lx,rx,mx,tag,sum,l,r;
}tree[N<<2];
 
void Pushdown(int rt){
if(tree[rt].tag==1){
    tree[rt<<1].tag=1;
    tree[rt<<1|1].tag=1;
    tree[rt<<1].lx=tree[rt<<1].rx=tree[rt<<1].mx=0;
    tree[rt<<1].sum=tree[rt<<1].r-tree[rt<<1].l+1;
    tree[rt<<1|1].lx=tree[rt<<1|1].rx=tree[rt<<1|1].mx=0;
    tree[rt<<1|1].sum=tree[rt<<1|1].r-tree[rt<<1|1].l+1;
    tree[rt].tag=0;
}
if(tree[rt].tag==-1){
    tree[rt<<1].tag=-1;
    tree[rt<<1|1].tag=-1;
    tree[rt<<1].lx=tree[rt<<1].rx=tree[rt<<1].mx=tree[rt<<1].r-tree[rt<<1].l+1;
    tree[rt<<1].sum=0;
    tree[rt<<1|1].lx=tree[rt<<1|1].rx=tree[rt<<1|1].mx=tree[rt<<1|1].rx=tree[rt<<1|1].mx=tree[rt<<1|1].r-tree[rt<<1|1].l+1;
    tree[rt<<1|1].sum=0;
    tree[rt].tag=0;
}
}
 
void Pushup(int rt){
tree[rt].mx=max(max(tree[rt<<1].mx,tree[rt<<1|1].mx),tree[rt<<1].rx+tree[rt<<1|1].lx);
tree[rt].lx=tree[rt<<1].lx;tree[rt].rx=tree[rt<<1|1].rx;
if(tree[rt<<1].lx==tree[rt<<1].r-tree[rt<<1].l+1)tree[rt].lx=tree[rt<<1].lx+tree[rt<<1|1].lx;
if(tree[rt<<1|1].rx==tree[rt<<1|1].r-tree[rt<<1|1].l+1)tree[rt].rx=tree[rt<<1|1].rx+tree[rt<<1].rx;
tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;
}
 
void Build(int rt,int l,int r){
tree[rt].l=l;tree[rt].r=r;
if(l==r){tree[rt].mx=tree[rt].lx=tree[rt].rx=0;tree[rt].sum=1;return;}
int mid=l+r>>1;
Build(rt<<1,l,mid);
Build(rt<<1|1,mid+1,r);
Pushup(rt);
}
 
void Update(int rt,int l,int r,int val){
if(l<=tree[rt].l && tree[rt].r<=r){
    tree[rt].tag=val;
    if(val==-1){tree[rt].lx=tree[rt].rx=tree[rt].mx=tree[rt].r-tree[rt].l+1;tree[rt].sum=0;}
    if(val==1){tree[rt].lx=tree[rt].rx=tree[rt].mx=0;tree[rt].sum=tree[rt].r-tree[rt].l+1;}
    return;
}
Pushdown(rt);
int mid=tree[rt].l+tree[rt].r>>1;
if(l<=mid)Update(rt<<1,l,r,val);
if(r>mid)Update(rt<<1|1,l,r,val);
Pushup(rt);
}
 
int GetSum(int rt,int l,int r){
if(l<=tree[rt].l & tree[rt].r<=r)return tree[rt].sum;
Pushdown(rt);
int mid=tree[rt].l+tree[rt].r>>1;
if(l>mid)return GetSum(rt<<1|1,l,r);
else if(r<=mid)return GetSum(rt<<1,l,r);
else return GetSum(rt<<1,l,r)+GetSum(rt<<1|1,l,r);
Pushup(rt);
}
 
void Solve(int l0,int r0,int l1,int r1){
int ResL=GetSum(1,l0,r0);
Update(1,l0,r0,-1);
int ResR=GetSum(1,l1,r1);
//printf("Res:%d %d\n",ResL,ResR);
if(ResL+ResR>=r1-l1+1){Update(1,l1,r1,1);/*puts("666!");*/}
else {
    int l=l1,r=r1;
    while(l<=r){
        int mid=l+r>>1,t=GetSum(1,l1,mid);
        if(mid-l1+1-t==ResL){Update(1,l1,mid,1);return;}
        else if(mid-l1+1<ResL+t)l=mid+1;
        else if(mid-l1+1>ResL+t)r=mid-1;
    }
}
}
 
SegTree Merge(SegTree L,SegTree R){
SegTree M;
M.mx=max(max(L.mx,R.mx),L.rx+R.lx);
M.lx=L.lx;M.rx=R.rx;
if(L.sum==0)M.lx=L.lx+R.lx;
if(R.sum==0)M.rx=L.rx+R.rx;
M.sum=max(L.sum,R.sum);
return M;
}
 
SegTree GetMax(int rt,int l,int r){
if(l<=tree[rt].l && tree[rt].r<=r)return tree[rt];
Pushdown(rt);
int mid=tree[rt].l+tree[rt].r>>1;
if(l>mid)return GetMax(rt<<1|1,l,r);
else if(r<=mid)return GetMax(rt<<1,l,r);
else {return Merge(GetMax(rt<<1,l,r),GetMax(rt<<1|1,l,r));}
Pushup(rt);
}
 
void Print(){
//puts("233:");
for(int i=1;i<=n;i++)printf("%d ",GetSum(1,i,i));
putchar('\n');
}
 
int main(){
freopen("4592.in","r",stdin);
freopen("4592.out","w",stdout);
scanf("%d %d",&n,&m);
Build(1,1,n);
//Print();
for(int i=1;i<=m;i++){
    int opt,l0,r0,l1,r1;
    scanf("%d %d %d",&opt,&l0,&r0);
    if(opt==1)scanf("%d %d",&l1,&r1);
    if(opt==0)Update(1,l0,r0,-1);
    if(opt==1)Solve(l0,r0,l1,r1);
    if(opt==2)printf("%d\n",GetMax(1,l0,r0).mx);
    //Print();
}
return 0;
}

考虑点分治

一棵一棵子树处理

用set判断一下有没有与len相等的值就可以了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<set>
#include<algorithm>
using namespace std;
 
const int N=10005,INF=2100000000;
 
int n,p,len[N],h[N],en,siz[N],vis[N],mx[N],val,root,ans[N],cnt;
long long dis[N*105];
set<long long> St;
 
struct Edge{
int b,next;
long long v;
}e[2*N];
 
void AddEdge(int sa,int sb,long long sc){
e[++en].b=sb;
e[en].v=sc;
e[en].next=h[sa];
h[sa]=en;
}
 
void DfsSiz(int u,int fa){
siz[u]=1;mx[u]=0;
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(fa!=v && !vis[v]){
        DfsSiz(v,u);
        siz[u]+=siz[v];
        mx[u]=max(mx[u],siz[v]);
    }
}
}
 
void DfsRoot(int point,int u,int fa){
mx[u]=max(mx[u],siz[point]-mx[u]);
if(val>mx[u]){val=mx[u];root=u;}
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(v!=fa && !vis[v])DfsRoot(point,v,u);
}
}
 
void Cal(int u,int fa,long long val){
for(int i=1;i<=p;i++)if(St.find(len[i]-val)!=St.end())ans[i]=1;
dis[++cnt]=val;
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(v!=fa & !vis[v])Cal(v,u,val+e[i].v);
}
}
 
void DFS(int u){
val=INF;
DfsSiz(u,u);
DfsRoot(u,u,0);
St.clear();
St.insert(0);
//printf("Root:%d\n",root);
vis[root]=1;
for(int i=h[root];i;i=e[i].next){
    int v=e[i].b;
    if(!vis[v]){
        cnt=0;
        //printf("%d %d\n",cnt,v);
        Cal(v,v,e[i].v);
        for(int j=1;j<=cnt;j++){St.insert(dis[j]);/*printf("%d\n",dis[j]);*/}
    }
}
for(int i=h[root];i;i=e[i].next){
    int v=e[i].b;
    if(!vis[v])DFS(v);
}
}

int main(){
freopen("1316.in","r",stdin);
freopen("1316.out","w",stdout);
scanf("%d %d",&n,&p);
for(int i=1;i<n;i++){
    int u,v,w;
    scanf("%d %d %d",&u,&v,&w);
    AddEdge(u,v,w);
    AddEdge(v,u,w);
}
for(int i=1;i<=p;i++)scanf("%d",&len[i]);
DFS(1);
for(int i=1;i<=p;i++)puts(ans[i]||!len[i]?"Yes":"No");
return 0;
}

二分最小值和最大值

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
 
const long long N=100005;
 
long long n,k,a[N],low,high,sum;
 
long long Test(long long x){
long long tx=0,nw=0;
for(long long i=1;i<=n;i++){
    nw+=a[i];
    if(nw<0)nw=0;
    if(nw>=x){tx++;nw=0;}
}
return tx;
}
 
long long Low(){
long long l=1,r=sum;
while(l<=r){
    long long mid=l+r>>1;
    if(Test(mid)<=k)r=mid-1;
    else l=mid+1;
}
return l;
}
 
long long High(){
long long l=1,r=sum;
while(l<=r){
    long long mid=l+r>>1;
    if(Test(mid)<k)r=mid-1;
    else l=mid+1;
}
return r;
}

int main(){
freopen("4590.in","r",stdin);
freopen("4590.out","w",stdout);
scanf("%lld %lld",&n,&k);
for(long long i=1;i<=n;i++){scanf("%lld",&a[i]);if(a[i]>0)sum+=a[i];}
low=Low();
high=High();
if(Test(low)!=k || Test(high)!=k){puts("-1");return 0;}
printf("%lld %lld\n",low,high);
return 0;
}