danihao123's Blog

万年不更的zzs出现了……

这个题以前竟然没做……近几天做了一下，首交竟然unAC……看样子是我真不会线段树了。

这题不难，唯一需要注意的是乘法标记对加法标记也有影响，而且下传要乘法优先。

代码（警告：此代码exciting）：

/**************************************************************
    Problem: 1798
    User: danihao123
    Language: C++
    Result: Accepted
    Time:7696 ms
    Memory:10980 kb
****************************************************************/
 
#include <cstdio>
typedef long long ll;
const int maxn=100005;
ll ha;
struct Node{
    ll sumv;
    int L,R;
    ll addv,mulv;
    Node *lc,*rc;
    Node(ll v,int pos){
        sumv=v%ha;
        addv=0;
        mulv=1;
        L=R=pos;
        lc=rc=NULL;
    }
    Node(Node *l,Node *r,int Le,int Ri){
        sumv=0;
        addv=0;
        mulv=1;
        L=Le;
        R=Ri;
        lc=l;
        rc=r;
    }
    void paint_add(ll v){
        v=v%ha;
        addv=(addv+v)%ha;
        ll add_v=(v*((R-L+1)%ha))%ha;
        sumv=(sumv+add_v)%ha;
    }
    void paint_mul(ll v){
        v=v%ha;
        addv=(addv*v)%ha;
        mulv=(mulv*v)%ha;
        sumv=(sumv*v)%ha;
    }
    void maintain(){
        if(lc!=NULL && rc!=NULL){
            sumv=(lc->sumv+rc->sumv)%ha;
        }
    }
    void pushdown(){
        if(mulv!=1){
            if(lc!=NULL){
                lc->paint_mul(mulv);
            }
            if(rc!=NULL){
                rc->paint_mul(mulv);
            }
            mulv=1;
        }
        if(addv!=0){
            if(lc!=NULL){
                lc->paint_add(addv);
            }
            if(rc!=NULL){
                rc->paint_add(addv);
            }
            addv=0;
        }
    }
};
 
ll A[maxn];
void build_tree(Node* &o,int L,int R){
    if(L==R){
        o=new Node(A[L],L);
    }else{
        int M=L+(R-L)/2;
        Node *lc,*rc;
        build_tree(lc,L,M);
        build_tree(rc,M+1,R);
        o=new Node(lc,rc,L,R);
        o->maintain();
    }
}
Node *root;
int ql,qr;
ll v;
ll query_sum(Node *o){
    int L=o->L,R=o->R;
    o->pushdown();
    if(ql<=L && R<=qr){
        return o->sumv;
    }else{
        int M=L+(R-L)/2;
        ll ans=0;
        if(ql<=M){
            ans=(ans+query_sum(o->lc))%ha;
        }
        if(qr>M){
            ans=(ans+query_sum(o->rc))%ha;
        }
        return ans;
    }
}
void update_add(Node *o){
    int L=o->L,R=o->R;
    o->pushdown();
    if(ql<=L && R<=qr){
        o->paint_add(v);
    }else{
        int M=L+(R-L)/2;
        if(ql<=M){
            update_add(o->lc);
        }
        if(qr>M){
            update_add(o->rc);
        }
        o->maintain();
    }
}
void update_mul(Node *o){
    int L=o->L,R=o->R;
    o->pushdown();
    if(ql<=L && R<=qr){
        o->paint_mul(v);
    }else{
        int M=L+(R-L)/2;
        if(ql<=M){
            update_mul(o->lc);
        }
        if(qr>M){
            update_mul(o->rc);
        }
        o->maintain();
    }
}
 
int main(){
    register int i;
    int n,m,op;
    scanf("%d%lld",&n,&ha);
    // ha=0x7fffffff;
    for(i=1;i<=n;i++){
        scanf("%lld",&A[i]);
    }
    build_tree(root,1,n);
    scanf("%d",&m);
    while(m--){
        scanf("%d%d%d",&op,&ql,&qr);
        if(ha==1){
            if(op==3){
                puts("0");
            }else{
                scanf("%lld",&v);
            }
            continue;
        }
        if(op==1){
            scanf("%lld",&v);
            update_mul(root);
        }else{
            if(op==2){
                scanf("%lld",&v);
                update_add(root);
            }else{
                printf("%lld\n",query_sum(root));
            }
        }
    }
    return 0;
}

这个题需要一些脑洞。

给出任意三点，如果我们两两求LCA，肯定有两组相同，剩下那一组就是最优集合点了。为啥？画图理解一下吧……

代码：

/**************************************************************
    Problem: 1787
    User: danihao123
    Language: C++
    Result: Accepted
    Time:4068 ms
    Memory:80900 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define GRAPH_REP(i,u) for(i=first[(u)];i;i=next[i])
#define TWO_POW(n) (1<<(n))
 
const int maxn=500001,maxm=1000001;
int first[maxn];
int next[maxm],to[maxm],dist[maxm];
int graph_cnt=0;
inline void Add_Edge(int u,int v,int d){
    graph_cnt++;
    next[graph_cnt]=first[u];
    first[u]=graph_cnt;
    to[graph_cnt]=v;
    dist[graph_cnt]=d;
}
 
int d[maxn];
int dep[maxn];
int anc[maxn][32];
void dfs(int x,int father,int depth,int dis){
    d[x]=dis;
    anc[x][0]=father;
    dep[x]=depth;
    int i;
    GRAPH_REP(i,x){
        if(to[i]!=father)
            dfs(to[i],x,depth+1,dis+dist[i]);
    }
}
 
int n;
inline void InitLCA(){
    register int i,j;
    for(j=1;TWO_POW(j)<n;j++){
        REP_B(i,n){
            if(anc[i][j-1]!=-1){
                anc[i][j]=anc[anc[i][j-1]][j-1];
            }
        }
    }
}
 
int QueryLCA(int x,int y){
    register int j,log;
    if(dep[x]<dep[y])
        swap(x,y);
    for(log=1;TWO_POW(log)<=dep[x];log++);
    log--;
    for(j=log;j>=0;j--)
        if(dep[x]-TWO_POW(j)>=dep[y])
            x=anc[x][j];
    if(x==y)
        return y;
    for(j=log;j>=0;j--){
        if(anc[x][j]!=-1 && anc[x][j]!=anc[y][j]){
            x=anc[x][j];
            y=anc[y][j];
        }
    }
    return anc[x][0];
}
inline int make_dis(int x,int y){
    return d[x]+d[y]-2*d[QueryLCA(x,y)];
}
 
int main(){
    int u,v,D;
    int x,y,z,QinDing;
    int m;
    register int i,j;
    scanf("%d%d",&n,&m);
    REP(i,n-1){
        scanf("%d%d",&u,&v);
        Add_Edge(u,v,1);
        Add_Edge(v,u,1);
    }
    memset(anc,-1,sizeof(anc));
    dfs(1,-1,0,0);
    InitLCA();
    REP(i,m){
        scanf("%d%d%d",&u,&v,&D);
        x=QueryLCA(u,v);
        y=QueryLCA(u,D);
        z=QueryLCA(v,D);
        if(x==y){
            QinDing=z;
        }else{
            if(x==z){
                QinDing=y;
            }else{
                QinDing=x;
            }
        }
        printf("%d %d\n",QinDing,make_dis(QinDing,u)+make_dis(QinDing,v)+make_dis(QinDing,D));
    }
    return 0;
}

妙，妙啊！

此乃数学之大道也

直接递推+求约数会炸，但是……

你可以枚举约数x，然后求出区间内约数有它的个数，很明显是\( \lfloor n \div x \rfloor \)，然后求和就行了……

代码：