Codeforces Round 907 (Div. 2)

\(A. Sorting with Twos\)

https://codeforces.com/contest/1891/submission/232689614

\(B. Deja Vu\)

https://codeforces.com/contest/1891/submission/232690141

\(C. Smilo and Monsters\)

https://codeforces.com/contest/1891/submission/232691988

\(D. Suspicious logarithms\)

这题的思路很好想，但是精度一直爆。后来vp结束int全部换int128就过了。
https://codeforces.com/contest/1891/submission/232694691

#define int __int128
vector<int>mi2(70);
int qmi(int m, int k, __int128 p){
    __int128 res = 1 % p, t = m;
    while (k){
        if (k&1) res = res * t % p;
        t = t * t % p;
        k >>= 1;
    }
    return res;
}
int lg(int x,int y){
    int p = 0,s = 1;
    while(s <= y) s *= x,p ++;
    return p - 1;
}
void solve(){
    int L=read(),R=read(),ans=0;
    for(int i=2;i<=62;i++){
        int mil=mi2[i],mir=mi2[i+1]-1;    
        if(mil<=R&&mir>=L){
            int ll=max(L,mil),rr=min(R,mir);
            int lval=(int)(lg(i,ll)),rval=(int)(lg(i,rr));
            if(lval==rval){
                ans+=lval*(rr-ll+1)%mod;
                ans%=mod;
            }else{
                int hh=qmi(i,rval,mod);
                ans+=lval*(hh-ll)%mod;
                ans%=mod;
                ans+=rval*(rr-hh+1)%mod;
                ans%=mod;
            }
        }else{
            continue;
        }
    }
    cout<<(long long)((ans+mod)%mod)<<'\n';
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}
signed main(){
    // ios::sync_with_stdio(false);
    // cin.tie(0);
    // cout.tie(0);
    // int t=1;
    mi2[0]=1;
    for(int i=1;i<=62;i++){
        mi2[i]=mi2[i-1]*2;
        // cout<<mi2[i]<<" ";
    }
    // cout<<'\n';
   int t=read();
    while(t--){
        solve();
    }
}

\(F. A Growing Tree\)

题意翻译：
\(T\) 组数据：
给定一棵树，初始只含一个节点，编号为 \(1\)，初始权值为 \(0\) ，设树的大小为 \(sz\) 。
\(q\) 次操作：
操作1: \(1\) \(x\) ，在 \(x\) 下挂一个节点，编号为 \(sz+1\) ，初始权值为 \(0\) 。
操作2: \(2\) \(x\) \(v\) ，将当前 \(x\) 子树中节点的权值加上 \(v\) 。
求所有操作完成后每个节点的点权。其中 \(1\le T\le 10^4,\sum q\le 5*10^5\) 。

做法：
考虑先离线把树建出来，一个点能受到 \(2\) 操作的影响当且仅当此操作的 \(x\) 是它的祖先且这个操作的时间晚于当前点被加入的时间。所以 \(dfs\) 一遍，用树状数组维护当前点到根的路径上，时间上的增量。对于每个点查询时间大于当前点加入的时间的操作的贡献即可。在回溯的时候，将当前点的操作撤销掉。

https://codeforces.com/contest/1891/submission/232698657

int h[N], e[N], ne[N], idx;
void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
int tim[N],ans[N],cnt,n;
vector<array<int,2> >vec[N];
struct Fenwick {
    int c[N+5];
    inline int lowbit(int x) {return x&(-x);}
    inline void add(int x,int d) {
        for(;x<=n;x+=lowbit(x))c[x]+=d;
    }
    inline int query(int x) {
        int res=0;
        for(;x>=1;x-=lowbit(x))res+=c[x];
        return res;
    }
    inline int rangequery(int l,int r) {
        return query(r)-query(l-1);
    }
}fen;
void dfs(int u){
    for(auto x:vec[u]){
        fen.add(x[0],x[1]);
        // cout<<x[0]<<" "<<x[1]<<'\n';
    }
    // cout<<n<<'\n';
    // cout<<u<<" "<<fen.query(n)<<'\n';
    ans[u]=fen.rangequery(tim[u],n);
    for (int i = h[u]; i != -1; i = ne[i]){
        int j = e[i];
        dfs(j);
    }
    for(auto x:vec[u]){
        fen.add(x[0],-x[1]);
    }
}
void solve(){
    idx = 0;cnt=1;
    // memset(h, -1, sizeof h);
    n=read();
    for(int i=0;i<=n;i++){
        vec[i].clear();
        fen.c[i]=0;
        h[i]=-1;
    }
    for(int i=1;i<=n;i++){
        int op=read();
        if(op==1){
            int u=read();
            tim[++cnt]=i;
            add(u,cnt);
        }else{
            vec[read()].push_back((array<int,2>){i,read()});
        }
    }
    dfs(1);
    for(int i=1;i<=cnt;i++){
        cout<<ans[i]<<" ";
    }
    cout<<'\n';
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}