\(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");
}