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 long double ld;
  22. typedef vector<int> vi;
  23. typedef vector<ll> vll;
  24. typedef pair<int, int> pii;
  25. typedef pair<ll, ll> pll;
  26. typedef vector<pii> vpii;
  27. typedef vector<pll> vpll;
  28.  
  29. const int mod=1e9+7;
  30. const int maxn=1e5+15;
  31. const ll inf=4e18;
  32.  
  33. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  34. ll ran(ll l, ll r)
  35. {
  36.     return uniform_int_distribution<ll> (l, r)(rng);
  37. }
  38.  
  39. inline void rf(){
  40.     ios_base::sync_with_stdio(false);
  41.     cin.tie(nullptr); cout.tie(nullptr);
  42.     if(fopen(file".inp","r")){
  43.         freopen(file".inp","r",stdin); freopen(file".out","w",stdout);
  44.     }
  45. }
  46.  
  47. template<typename T> inline void add(T &x, const T &y)
  48. {
  49.     x+=y;
  50.     if(x>=mod) x-=mod;
  51.     if(x<0) x+=mod;
  52. }
  53.  
  54. template<typename T> inline bool maxi(T &a, T b)
  55. {
  56.     if(a>=b) return 0;
  57.     a=b; return 1;
  58. }
  59.  
  60. template<typename T> inline bool mini(T &a, T b)
  61. {
  62.     if(a<=b) return 0;
  63.     a=b; return 1;
  64. }
  65.  
  66. int n,q;
  67. ll a[maxn];
  68. vi g[maxn];
  69. int par[maxn], h[maxn], heavy[maxn], head[maxn], st[maxn], ed[maxn], siz[maxn], timer_=0;
  70.  
  71. vll spev;
  72. unordered_set<ll> spes;
  73.  
  74. inline string todecstr(ll x)
  75. {
  76.     if(x==0) return "0";
  77.     string s; while(x){ s+=char('0'+(x%10)); x/=10; } reverse(all(s)); return s;
  78. }
  79.  
  80. inline ll palsub(const string &s)
  81. {
  82.     int m=sz(s);
  83.     ll ans=0;
  84.     ff(c,0,m-1){
  85.         int l=c, r=c;
  86.         while(l>=0 && r<m && s[l]==s[r]){ ++ans; --l; ++r; }
  87.     }
  88.     ff(c,0,m-2){
  89.         int l=c, r=c+1;
  90.         while(l>=0 && r<m && s[l]==s[r]){ ++ans; --l; ++r; }
  91.     }
  92.     return ans;
  93. }
  94.  
  95. inline bool valid(ll x)
  96. {
  97.     if(x<=0) return 0;
  98.     string s=todecstr(x);
  99.     int c3=0,c6=0;
  100.     for(char c:s)
  101.     {
  102.         if(c=='3') ++c3;
  103.         else if(c=='6') ++c6;
  104.         else return 0;
  105.     }
  106.     if(c3!=c6) return 0;
  107.     ll mau=1LL*sz(s)*(sz(s)+1)/2;
  108.     ll tu=palsub(s);
  109.     return tu*2>mau;
  110. }
  111.  
  112. void gen(ll x)
  113. {
  114.     if(x>1e16) return;
  115.     if(x!=0 && valid(x)) spev.pb(x);
  116.     if(x==0){ gen(3); gen(6); }
  117.     else
  118.     {
  119.         if(x<=1e15){ gen(x*10+3); gen(x*10+6); }
  120.     }
  121. }
  122.  
  123. int dfs1(int u, int p)
  124. {
  125.     par[u]=p; siz[u]=1; int mx=0; heavy[u]=0;
  126.     for(int v:g[u]) if(v!=p)
  127.     {
  128.         h[v]=h[u]+1;
  129.         int s=dfs1(v,u);
  130.         siz[u]+=s;
  131.         if(s>mx){ mx=s; heavy[u]=v; }
  132.     }
  133.     return siz[u];
  134. }
  135. void dfs2(int u, int hd)
  136. {
  137.     head[u]=hd; st[u]=++timer_;
  138.     if(heavy[u]) dfs2(heavy[u], hd);
  139.     for(int v:g[u]) if(v!=par[u] && v!=heavy[u]) dfs2(v, v);
  140.     ed[u]=timer_;
  141. }
  142.  
  143. struct BLK 
  144. {
  145.     int N,B,NB;
  146.     vll val, tag;
  147.     vector<unordered_map<ll,int>> freq;
  148.     inline int bid(int i) const { return (i-1)/B; }
  149.     inline int bl(int b) const { return b*B+1; }
  150.     inline int br(int b) const { return min(N, (b+1)*B); }
  151.     void init(int n, int B_=512)
  152.     {
  153.         N=n; B=max(256,B_); NB=(N+B-1)/B;
  154.         val.assign(N+1,0); tag.assign(NB,0);
  155.         freq.assign(NB, {});
  156.     }
  157.     void build(const vll &base)
  158.     {
  159.         ff(i,1,N) val[i]=base[i];
  160.         ff(b,0,NB-1)
  161.         {
  162.             freq[b].clear();
  163.             ff(i,bl(b),br(b)) ++freq[b][val[i]];
  164.         }
  165.     }
  166.     void range_add(int l, int r, ll x)
  167.     {
  168.         if(l>r) return;
  169.         int blid=bid(l), brid=bid(r);
  170.         if(blid==brid)
  171.         {
  172.             auto &F=freq[blid];
  173.             ff(i,l,r)
  174.             {
  175.                 ll oldv=val[i];
  176.                 auto it=F.find(oldv);
  177.                 if(it!=F.end()){ if(--(it->se)==0) F.erase(it); }
  178.                 val[i]=oldv+x;
  179.                 ++F[val[i]];
  180.             }
  181.             return;
  182.         }
  183.         {
  184.             auto &F=freq[blid];
  185.             ff(i,l,br(blid))
  186.             {
  187.                 ll oldv=val[i];
  188.                 auto it=F.find(oldv);
  189.                 if(it!=F.end()){ if(--(it->se)==0) F.erase(it); }
  190.                 val[i]=oldv+x;
  191.                 ++F[val[i]];
  192.             }
  193.         }
  194.         ff(b,blid+1,brid-1) tag[b]+=x;
  195.         {
  196.             auto &F=freq[brid];
  197.             ff(i,bl(brid),r)
  198.             {
  199.                 ll oldv=val[i];
  200.                 auto it=F.find(oldv);
  201.                 if(it!=F.end()){ if(--(it->se)==0) F.erase(it); }
  202.                 val[i]=oldv+x;
  203.                 ++F[val[i]];
  204.             }
  205.         }
  206.     }
  207.     ll range_cnt(int l, int r) const
  208.     {
  209.         if(l>r) return 0;
  210.         ll ans=0;
  211.         int blid=bid(l), brid=bid(r);
  212.         if(blid==brid)
  213.         {
  214.             ll tg=tag[blid];
  215.             ff(i,l,r)
  216.             {
  217.                 ll realv=val[i]+tg;
  218.                 if(spes.find(realv)!=spes.end()) ++ans;
  219.             }
  220.             return ans;
  221.         }
  222.         {
  223.             ll tg=tag[blid];
  224.             ff(i,l,br(blid)){
  225.                 ll realv=val[i]+tg;
  226.                 if(spes.find(realv)!=spes.end()) ++ans;
  227.             }
  228.         }
  229.         ff(b,blid+1,brid-1)
  230.         {
  231.             ll tg=tag[b];
  232.             const auto &F=freq[b];
  233.             for(const auto &kv:F)
  234.             {
  235.                 ll realv=kv.fi+tg;
  236.                 if(spes.find(realv)!=spes.end()) ans+=kv.se;
  237.             }
  238.         }
  239.         {
  240.             ll tg=tag[brid];
  241.             ff(i,bl(brid),r)
  242.             {
  243.                 ll realv=val[i]+tg;
  244.                 if(spes.find(realv)!=spes.end()) ++ans;
  245.             }
  246.         }
  247.         return ans;
  248.     }
  249. } T;
  250.  
  251. inline void upd_path(int u, int v, ll x)
  252. {
  253.     while(head[u]!=head[v]){
  254.         if(h[head[u]]<h[head[v]]) swap(u,v);
  255.         T.range_add(st[head[u]], st[u], x);
  256.         u=par[head[u]];
  257.     }
  258.     if(h[u]>h[v]) swap(u,v);
  259.     T.range_add(st[u], st[v], x);
  260. }
  261.  
  262. inline ll get_path(int u, int v)
  263. {
  264.     ll ans=0;
  265.     while(head[u]!=head[v])
  266.     {
  267.         if(h[head[u]]<h[head[v]]) swap(u,v);
  268.         ans+=T.range_cnt(st[head[u]], st[u]);
  269.         u=par[head[u]];
  270.     }
  271.     if(h[u]>h[v]) swap(u,v);
  272.     ans+=T.range_cnt(st[u], st[v]);
  273.     return ans;
  274. }
  275.  
  276. inline ll get_sub(int u)
  277. {
  278.     return T.range_cnt(st[u], ed[u]);
  279. }
  280.  
  281. signed main(){
  282.     rf();
  283.     cin>>n>>q;
  284.     ff(i,1,n) cin>>a[i];
  285.     ff(i,1,n-1)
  286.     {
  287.         int u,v; cin>>u>>v;
  288.         g[u].pb(v); g[v].pb(u);
  289.     }
  290.     dfs1(1,0); dfs2(1,1);
  291.     vll base(timer_+1,0);
  292.     ff(i,1,n) base[st[i]]=a[i];
  293.     gen(0);
  294.     sort(all(spev)); spev.erase(unique(all(spev)), spev.end());
  295.     spes.reserve(spev.size()*2+7);
  296.     for(ll v:spev) spes.insert(v);
  297.     T.init(timer_,512);
  298.     T.build(base);
  299.     while(q--)
  300.     {
  301.         int op; cin>>op;
  302.         if(op==1)
  303.         {
  304.             int u,v; ll x; cin>>u>>v>>x;
  305.             upd_path(u,v,x);
  306.         }
  307.         else if(op==2)
  308.         {
  309.             int u,v; cin>>u>>v;
  310.             cout<<get_path(u,v)<<nl;
  311.         }
  312.         else
  313.         {
  314.             int u; cin>>u;
  315.             cout<<get_sub(u)<<nl;
  316.         }
  317.     }
  318.     re;
  319. }
  320.  
Success #stdin #stdout 0.03s 7712KB
comments (?)
stdin
copy 
5 7
0 0 0 0 0
1 2
1 3
3 5
3 4
1 2 4 3
1 5 5 3
1 2 5 33
1 4 4 33
2 1 4
2 2 3
3 3
stdout
copy 
3
3
3
https://ideone.com/7RQzyQ
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!