danihao123's Blog

[BZOJ 1798]维护序列

万年不更的zzs出现了……

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

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

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

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

/**************************************************************
    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;
}

[BZOJ 1787]紧急集合

这个题需要一些脑洞。

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

代码：

100

101

102

103

104

105

106

107

108

109

110

111

/**************************************************************
    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;
}

[BZOJ 1968]约数研究

妙，妙啊！

此乃数学之大道也

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

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

代码：

继续阅读

[BZOJ 1798]维护序列

[BZOJ 1787]紧急集合

[BZOJ 1968]约数研究

danihao123

搜索

分类

标签云

最新评论

最新留言

神犇的Blog

RSS

功能

计数器