fork download
copy 
  1. //#pragma GCC optimize("Ofast,unroll-loops")
  2. //#pragma GCC target("avx2,tune=native")
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. #define file "fakernum"
  7. #define ff(i,a,b) for(auto i=(a); i<=(b); ++i)
  8. #define ffr(i,b,a) for(auto i=(b); i>=(a); --i)
  9. #define nl "\n"
  10. #define ss " "
  11. #define pb emplace_back
  12. #define fi first
  13. #define se second
  14. #define sz(s) (int)(s).size()
  15. #define all(s) (s).begin(), (s).end()
  16. #define ms(a,x) memset(a, x, sizeof(a))
  17. #define cn continue
  18. #define re exit(0)
  19.  
  20. typedef long long ll;
  21. typedef unsigned long long ull;
  22. typedef long double ld;
  23. typedef vector<int> vi;
  24. typedef vector<ll> vll;
  25. typedef pair<int,int> pii;
  26. typedef pair<ll,ll> pll;
  27. typedef vector<pii> vpii;
  28. typedef vector<pll> vpll;
  29.  
  30. const int mod=1e9+7;
  31. const int maxn=1e5+15;
  32. const ll inf=4e18;
  33. const ll LIMV = 10000000000000000LL;
  34.  
  35. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  36. ll ran(ll l, ll r){ return uniform_int_distribution<ll>(l,r)(rng); }
  37.  
  38. inline void rf(){
  39.     ios_base::sync_with_stdio(false);
  40.     cin.tie(nullptr); cout.tie(nullptr);
  41.     if(fopen(file".inp","r")){
  42.         freopen(file".inp","r",stdin); freopen(file".out","w",stdout);
  43.     }
  44. }
  45.  
  46. template<typename T> inline void addm(T &x, const T &y){ x+=y; if(x>=mod) x-=mod; if(x<0) x+=mod; }
  47. template<typename T> inline bool maxi(T &a, T b){ if(a>=b) return 0; a=b; return 1; }
  48. template<typename T> inline bool mini(T &a, T b){ if(a<=b) return 0; a=b; return 1; }
  49.  
  50. int n,q;
  51. ll a[maxn];
  52. vi g[maxn];
  53. int par[maxn], h[maxn], heavy[maxn], head[maxn], st[maxn], ed[maxn], siz[maxn], timer_=0;
  54.  
  55. vll spev;
  56. unordered_set<ll> spes;
  57.  
  58. inline string todecstr(ll x){
  59.     if(x==0) return "0";
  60.     string s; while(x){ s+=char('0'+(x%10)); x/=10; } reverse(all(s)); return s;
  61. }
  62. inline long long palsub(const string &s){
  63.     int m=sz(s);
  64.     long long ans=0;
  65.     ff(c,0,m-1){
  66.         int l=c, r=c;
  67.         while(l>=0 && r<m && s[l]==s[r]){ ++ans; --l; ++r; }
  68.     }
  69.     ff(c,0,m-2){
  70.         int l=c, r=c+1;
  71.         while(l>=0 && r<m && s[l]==s[r]){ ++ans; --l; ++r; }
  72.     }
  73.     return ans;
  74. }
  75. inline bool valid(ll x){
  76.     if(x<=0) return 0;
  77.     string s=todecstr(x);
  78.     int c3=0,c6=0;
  79.     for(char c:s){
  80.         if(c=='3') ++c3;
  81.         else if(c=='6') ++c6;
  82.         else return 0;
  83.     }
  84.     if(c3!=c6) return 0;
  85.     long long mau=1LL*sz(s)*(sz(s)+1)/2;
  86.     long long tu=palsub(s);
  87.     return tu*2>mau;
  88. }
  89. void gen(ll x){
  90.     if(x>LIMV) return;
  91.     if(x!=0 && valid(x)) spev.pb(x);
  92.     if(x==0){ gen(3); gen(6); }
  93.     else{
  94.         if(x<=LIMV/10){ gen(x*10+3); gen(x*10+6); }
  95.     }
  96. }
  97.  
  98. int dfs1(int u, int p){
  99.     par[u]=p; siz[u]=1; int mx=0; heavy[u]=0;
  100.     for(int v:g[u]) if(v!=p){
  101.         h[v]=h[u]+1;
  102.         int s=dfs1(v,u);
  103.         siz[u]+=s;
  104.         if(s>mx){ mx=s; heavy[u]=v; }
  105.     }
  106.     return siz[u];
  107. }
  108. void dfs2(int u, int hd){
  109.     head[u]=hd; st[u]=++timer_;
  110.     if(heavy[u]) dfs2(heavy[u], hd);
  111.     for(int v:g[u]) if(v!=par[u] && v!=heavy[u]) dfs2(v, v);
  112.     ed[u]=timer_;
  113. }
  114.  
  115. struct BLK {
  116.     int N,B,NB;
  117.     vll val, tag;
  118.     vector<unordered_map<ll,int>> freq;
  119.     inline int bid(int i) const { return (i-1)/B; }
  120.     inline int bl(int b) const { return b*B+1; }
  121.     inline int br(int b) const { return min(N, (b+1)*B); }
  122.     void init(int n, int B_=512){
  123.         N=n; B=max(256,B_); NB=(N+B-1)/B;
  124.         val.assign(N+1,0); tag.assign(NB,0);
  125.         freq.assign(NB, {});
  126.     }
  127.     void build(const vll &base){
  128.         ff(i,1,N) val[i]=base[i];
  129.         ff(b,0,NB-1){
  130.             freq[b].clear();
  131.             ff(i,bl(b),br(b)) ++freq[b][val[i]];
  132.         }
  133.     }
  134.     void range_add(int l, int r, ll x){
  135.         if(l>r) return;
  136.         int blid=bid(l), brid=bid(r);
  137.         if(blid==brid){
  138.             auto &F=freq[blid];
  139.             ff(i,l,r){
  140.                 ll oldv=val[i];
  141.                 auto it=F.find(oldv);
  142.                 if(it!=F.end()){ if(--(it->se)==0) F.erase(it); }
  143.                 val[i]=oldv+x;
  144.                 ++F[val[i]];
  145.             }
  146.             return;
  147.         }
  148.         {
  149.             auto &F=freq[blid];
  150.             ff(i,l,br(blid)){
  151.                 ll oldv=val[i];
  152.                 auto it=F.find(oldv);
  153.                 if(it!=F.end()){ if(--(it->se)==0) F.erase(it); }
  154.                 val[i]=oldv+x;
  155.                 ++F[val[i]];
  156.             }
  157.         }
  158.         ff(b,blid+1,brid-1) tag[b]+=x;
  159.         {
  160.             auto &F=freq[brid];
  161.             ff(i,bl(brid),r){
  162.                 ll oldv=val[i];
  163.                 auto it=F.find(oldv);
  164.                 if(it!=F.end()){ if(--(it->se)==0) F.erase(it); }
  165.                 val[i]=oldv+x;
  166.                 ++F[val[i]];
  167.             }
  168.         }
  169.     }
  170.     long long range_cnt(int l, int r) const{
  171.         if(l>r) return 0;
  172.         long long ans=0;
  173.         int blid=bid(l), brid=bid(r);
  174.         if(blid==brid){
  175.             ll tg=tag[blid];
  176.             ff(i,l,r){
  177.                 ll realv=val[i]+tg;
  178.                 if(spes.find(realv)!=spes.end()) ++ans;
  179.             }
  180.             return ans;
  181.         }
  182.         {
  183.             ll tg=tag[blid];
  184.             ff(i,l,br(blid)){
  185.                 ll realv=val[i]+tg;
  186.                 if(spes.find(realv)!=spes.end()) ++ans;
  187.             }
  188.         }
  189.         ff(b,blid+1,brid-1){
  190.             ll tg=tag[b];
  191.             const auto &F=freq[b];
  192.             for(const auto &kv:F){
  193.                 ll realv=kv.fi+tg;
  194.                 if(spes.find(realv)!=spes.end()) ans+=kv.se;
  195.             }
  196.         }
  197.         {
  198.             ll tg=tag[brid];
  199.             ff(i,bl(brid),r){
  200.                 ll realv=val[i]+tg;
  201.                 if(spes.find(realv)!=spes.end()) ++ans;
  202.             }
  203.         }
  204.         return ans;
  205.     }
  206. } T;
  207.  
  208. inline void upd_path(int u, int v, ll x){
  209.     while(head[u]!=head[v]){
  210.         if(h[head[u]]<h[head[v]]) swap(u,v);
  211.         T.range_add(st[head[u]], st[u], x);
  212.         u=par[head[u]];
  213.     }
  214.     if(h[u]>h[v]) swap(u,v);
  215.     T.range_add(st[u], st[v], x);
  216. }
  217. inline long long get_path(int u, int v){
  218.     long long ans=0;
  219.     while(head[u]!=head[v]){
  220.         if(h[head[u]]<h[head[v]]) swap(u,v);
  221.         ans+=T.range_cnt(st[head[u]], st[u]);
  222.         u=par[head[u]];
  223.     }
  224.     if(h[u]>h[v]) swap(u,v);
  225.     ans+=T.range_cnt(st[u], st[v]);
  226.     return ans;
  227. }
  228. inline long long get_sub(int u){
  229.     return T.range_cnt(st[u], ed[u]);
  230. }
  231.  
  232. signed main(){
  233.     rf();
  234.     cin>>n>>q;
  235.     ff(i,1,n) cin>>a[i];
  236.     ff(i,1,n-1){
  237.         int u,v; cin>>u>>v;
  238.         g[u].pb(v); g[v].pb(u);
  239.     }
  240.     dfs1(1,0); dfs2(1,1);
  241.     vll base(timer_+1,0);
  242.     ff(i,1,n) base[st[i]]=a[i];
  243.     gen(0);
  244.     sort(all(spev)); spev.erase(unique(all(spev)), spev.end());
  245.     spes.reserve(spev.size()*2+7);
  246.     for(ll v:spev) spes.insert(v);
  247.     T.init(timer_,512);
  248.     T.build(base);
  249.     while(q--){
  250.         int op; cin>>op;
  251.         if(op==1){
  252.             int u,v; ll x; cin>>u>>v>>x;
  253.             upd_path(u,v,x);
  254.         }else if(op==2){
  255.             int u,v; cin>>u>>v;
  256.             cout<<get_path(u,v)<<nl;
  257.         }else{
  258.             int u; cin>>u;
  259.             cout<<get_sub(u)<<nl;
  260.         }
  261.     }
  262.     re;
  263. }
  264.  
Success #stdin #stdout 0.04s 8472KB
comments (?)
stdin
copy 
7 5
30 30 57 60 36 63 27
1 2
1 3
2 7
3 4
4 5
4 6
3 1
3 4
1 4 7 6
3 1
2 3 7
stdout
copy 
2
2
5
3
https://ideone.com/jWrGTQ
language:
C++14 (gcc 8.3)
created:
12 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!