API tools faq
paste
_no0B

Untitled

_no0B
Apr 25th, 2019
126
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 24.68 KB | None | 0 0
raw download clone embed print report
  1. /// Mo's Algorithm On Trees
  2. #define LOG 18
  3. #define MAX 100010
  4. #define MAXQ 100010
  5. /// SPOJ Count On A Tree II, Number of distinct values on nodes on the path from U to V
  6. namespace mo{ /// Mo's Algorithm on Trees, 0-based index
  7.     int q, counter, block_size = 337, out[MAXQ], freq[MAX]; /// block_size = sqrt(2*N)
  8.     struct Query{
  9.         int l, r, s, d, idx;
  10.         inline Query() {}
  11.         inline Query(int a, int b, int p, int c){
  12.             idx = c;
  13.             l = a, r = b, s = p, d = l / block_size;
  14.         }
  15.         inline bool operator < (const Query& other) const{
  16.             if (d != other.d) return (d < other.d);
  17.             return ((d & 1) ? (r < other.r) : (r > other.r));
  18.         }
  19.     } Q[MAXQ];
  20.     vector <int> adj[MAX];
  21.     int n, r, t, S[MAX], E[MAX], ar[MAX << 1], parent[MAX], depth[MAX], lg[MAX], nodeval[MAX], nodecount[MAX], dp[MAX][LOG];
  22.     void init(int nodes, int root, int sz, int* nodevalT){ /// Values on nodes, modify appropriately if values on edges
  23.         lg[0] = lg[1] = 0;
  24.         block_size = max(1, sz);
  25.         clr(freq), clr(nodecount);
  26.         q = 0, t = 0, n = nodes, r = root;
  27.         for (int i = 0; i <= n; i++) adj[i].clear();
  28.         for (int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;
  29.         for (int i = 0; i < n; i++) nodeval[i] = nodevalT[i];
  30.     }
  31.     inline void add_edge(int u, int v){
  32.         adj[u].push_back(v);
  33.         adj[v].push_back(u);
  34.     }
  35.     inline int lca(int a, int b){
  36.         if (a == b) return a;
  37.         if (depth[a] < depth[b]) swap(a, b);
  38.         for (int i = lg[depth[a] - depth[b]]; i >= 0; i--){
  39.             if ((depth[a] - (1 << i)) >= depth[b]) a = dp[a][i];
  40.         }
  41.         if (a == b) return a;
  42.         for (int i = lg[depth[a]]; i >= 0; i--){
  43.             if (dp[a][i] != dp[b][i]){
  44.                 a = dp[a][i];
  45.                 b = dp[b][i];
  46.             }
  47.         }
  48.         return (a == b) ? a : parent[a];
  49.     }
  50.     inline void dfs(int i, int p){
  51.         S[i] = t, ar[t++] = i;
  52.         int j, len = adj[i].size();
  53.         for (j = 0, parent[i] = p; j < len; j++){
  54.             if (adj[i][j] != p){
  55.                 depth[adj[i][j]] = depth[i] + 1;
  56.                 dfs(adj[i][j], i);
  57.             }
  58.         }
  59.         E[i] = t, ar[t++] = i;
  60.     }
  61.     inline void build(){
  62.         depth[r] = 0;
  63.         dfs(r, r);
  64.         for (int l = 0; l <= lg[n]; l++){
  65.             for (int i = 0; i < n; i++){
  66.                 if (!l) dp[i][l] = parent[i];
  67.                 else dp[i][l] = dp[dp[i][l - 1]][l - 1];
  68.             }
  69.         }
  70.     }
  71.     inline void push(int a, int b, int idx){
  72.         if (depth[a] > depth[b]) swap(a, b);
  73.         int l = lca(a, b);
  74.         if (a == l) Q[q++] = Query(S[a], S[b], -1, idx);
  75.         else{
  76.             if (E[b] <= S[a]) Q[q++] = Query(E[b], S[a], S[l], idx);
  77.             else Q[q++] = Query(E[a], S[b], S[l], idx);
  78.         }
  79.     }
  80.     /// If a node occurs twice in a range, then both its value needs to be ignored
  81.     inline void insert(int idx){
  82.         int x = ar[idx];
  83.         if (nodecount[x]){
  84.             freq[nodeval[x]]--;
  85.             if (freq[nodeval[x]] == 0) counter--;
  86.         }
  87.         else{
  88.             if (freq[nodeval[x]] == 0) counter++;
  89.             freq[nodeval[x]]++;
  90.         }
  91.         nodecount[x] ^= 1;
  92.     }
  93.     inline void erase(int idx){
  94.         int x = ar[idx];
  95.         if (!nodecount[x]){
  96.             if (freq[nodeval[x]] == 0) counter++;
  97.             freq[nodeval[x]]++;
  98.         }
  99.         else{
  100.             freq[nodeval[x]]--;
  101.             if (freq[nodeval[x]] == 0) counter--;
  102.         }
  103.         nodecount[x] ^= 1;
  104.     }
  105.     inline void run(){
  106.         counter = 0;
  107.         sort(Q, Q + q);
  108.         int i, l, r, a = 0, b = 0; /// Change here if 1-based array
  109.         for (i = 0; i < q; i++){
  110.             l = Q[i].l, r = Q[i].r;
  111.             while (a > l) insert(--a);
  112.             while (b <= r) insert(b++);
  113.             while (a < l) erase(a++);
  114.             while (b > (r + 1)) erase(--b);
  115.             if (Q[i].s != -1) insert(Q[i].s);
  116.             out[Q[i].idx] = counter;
  117.             if (Q[i].s != -1) erase(Q[i].s);
  118.         }
  119.     }
  120.     inline void print(){
  121.         for (int i = 0; i < q; i++) printf("%d\n", out[i]);
  122.     }
  123. }
  124. int T[MAX], H[MAX];
  125. tr1::unordered_map <int, int> mp;
  126. int main(){
  127.     int n, q, h, i, j, k, a, b;
  128.     scanf("%d %d", &n, &q);
  129.     for (i = 0; i < n; i++) scanf("%d", &T[i]);
  130.     /// Co-ordinate compression, necessary only for this problem
  131.     /*** mp.clear();
  132.     for (h = 0, i = 0; i < n; i++) H[i] = T[i];
  133.     sort(H, H + n);
  134.     H[n] = -1;
  135.     for (i = 0; i < n; i++){
  136.         if (H[i] != H[i + 1]) mp[H[i]] = ++h;
  137.     }
  138.     for (i = 0; i < n; i++) T[i] = mp[T[i]]; ***/
  139.     mo::init(n, 0, 337, T);
  140.     for (i = 1; i < n; i++){
  141.         scanf("%d %d", &a, &b);
  142.         a--, b--;
  143.         mo::add_edge(a, b);
  144.     }
  145.     mo::build();
  146.     for (i = 0; i < q; i++) {
  147.         scanf("%d %d", &a, &b);
  148.         a--, b--;
  149.         mo::push(a, b, i);
  150.     }
  151.     mo::run();
  152.     mo::print();
  153.     return 0;
  154. }
  155.  
  156.  
  157.  
  158. /// MO's algo
  159. #define MAXN 200010
  160. #define MAXQ 200010
  161. #define MAXV 1000010
  162. /// 0 based index for arrays and queries
  163. const int block_size = 633;
  164. long long res, out[MAXQ];
  165. int n, q, ar[MAXN], freq[MAXV];
  166. struct query{
  167.     int l, r, d, i;
  168.     inline query() {}
  169.     inline query(int a, int b, int c){
  170.         i = c;
  171.         l = a, r = b, d = l / block_size;
  172.     }
  173.     inline bool operator < (const query& other) const{
  174.         if (d != other.d) return (d < other.d);
  175.         return ((d & 1) ? (r < other.r) : (r > other.r));
  176.     }
  177. } Q[MAXQ];
  178. inline void insert(int i){
  179.     res += (long long)ar[i] * (1 + 2 * freq[ar[i]]++);
  180. }
  181. inline void erase(int i){
  182.     res -= (long long)ar[i] * (1 + 2 * --freq[ar[i]]);
  183. }
  184. inline void run(){ /// hash = 812195
  185.     sort(Q, Q + q);
  186.     int i, l, r, a = 0, b = 0;
  187.     for (res = 0, i = 0; i < q; i++){
  188.         l = Q[i].l, r = Q[i].r;
  189.         while (a > l) insert(--a);
  190.         while (b <= r) insert(b++);
  191.         while (a < l) erase(a++);
  192.         while (b > (r + 1)) erase(--b);
  193.         out[Q[i].i] = res;
  194.     }
  195.     for (i = 0; i < q; i++) printf("%lld\n", out[i]);
  196. }
  197. int main(){
  198.     int n, i, j, k, a, b;
  199.     scanf("%d %d", &n, &q);
  200.     for (i = 0; i < n; i++) scanf("%d", &ar[i]);
  201.     for (i = 0; i < q; i++){
  202.         scanf("%d %d", &a, &b);
  203.         Q[i] = query(a - 1, b - 1, i);
  204.     }
  205.     run();
  206.     return 0;
  207. }
  208.  
  209.  
  210.  
  211. /// Radix Sort
  212. #define CHUNK 8
  213. #define MAX 1000010
  214. int n;
  215. unsigned int bucket[1 << CHUNK], ar[MAX + 10], temp[MAX + 10];
  216. void radix_sort(unsigned int* ar, int n){
  217.     int i, j, x;
  218.     const int bitmask = (1 << CHUNK) - 1;
  219.     for (i = 0; i < 32; i += CHUNK){
  220.         clr(bucket);
  221.         for (j = 0; j < n; j++) bucket[(ar[j] >> i) & bitmask]++;
  222.         for (j = 1; j <= bitmask; j++){
  223.             bucket[j] += bucket[j - 1];
  224.         }
  225.         for (j = n - 1; j >= 0; j--) temp[--bucket[(ar[j] >> i) & bitmask]] = ar[j];
  226.         for (j = 0; j < n; j++) ar[j] = temp[j];
  227.     }
  228. }
  229. int main(){
  230.     n = MAX;
  231.     srand(time(0));
  232.     int i, j, k, x, y;
  233.     for (i = 0; i < n; i++) ar[i] = (rand() * rand());
  234.     clock_t start = clock();
  235.     radix_sort(ar, n);
  236.     for (i = 0; (i + 1) < n; i++){
  237.         if (ar[i] > ar[i + 1]) puts("YO");
  238.     }
  239.     printf("%0.5f s\n", (clock() - start) / (1.0 * CLOCKS_PER_SEC));
  240.     return 0;
  241. }
  242.  
  243.  
  244. /// Treap (Static)
  245. #define MAXN 200010
  246. struct node{
  247.     node *l, *r;
  248.     int key, subtree, priority;
  249.     inline node(){
  250.         l = r = 0;
  251.     }
  252.     inline node(int val){
  253.         l = r = 0;
  254.         subtree = 1, key = val;
  255.         priority = (rand() << 16) ^ rand();
  256.     }
  257.     inline void update(){
  258.         subtree = 1;
  259.         if (l) subtree += l->subtree;
  260.         if (r) subtree += r->subtree;
  261.     }
  262. } pool[MAXN]; /// Maximum number of nodes in treap
  263. struct Treap{
  264.     int idx; /// Make global if multiple copy of treaps required as of some moment
  265.     struct node* root;
  266.     inline void merge(node* &cur, node* l, node* r){
  267.         if (!l || !r) cur = l ? l : r;
  268.         else if (l->priority > r->priority) merge(l->r, l->r, r), cur = l;
  269.         else merge(r->l, l, r->l), cur = r;
  270.         if (cur) cur->update();
  271.     }
  272.     /// Splits treap into 2 treaps l and r such that all values in l <= key and all values in r > key
  273.     inline void split(node* cur, node* &l, node* &r, int key){
  274.         if (!cur) l = r = 0;
  275.         else if (key <= cur->key) split(cur->l, l, cur->l, key), r = cur;
  276.         else split(cur->r, cur->r, r, key), l = cur;
  277.         if (cur) cur->update();
  278.     }
  279.     inline void insert(node* &cur, node* it){
  280.         if (!cur) cur = it;
  281.         else if (it->priority > cur->priority) split(cur, it->l, it->r, it->key), cur = it;
  282.         else insert((it->key < cur->key)? cur->l : cur->r, it);
  283.         if (cur) cur->update();
  284.     }
  285.     inline void erase(node* &cur, int key){
  286.         if (!cur) return;
  287.         if (cur->key == key) merge(cur, cur->l, cur->r);
  288.         else erase((cur->key > key) ? cur->l : cur->r, key);
  289.         if (cur) cur->update();
  290.     }
  291.     Treap(){
  292.         srand(time(0));
  293.         idx = 0, root = 0; /// Remove idx = 0 and include in main to reset all
  294.                           /// if multiple copy of treaps required as of some moment
  295.     }
  296.     inline void insert(int key){
  297.         pool[idx] = node(key);
  298.         insert(root, &pool[idx++]);
  299.     }
  300.     inline void erase(int key){
  301.         erase(root, key);
  302.     }
  303.     inline int size(){
  304.         if (root) return root->subtree;
  305.         return 0;
  306.     }
  307.     /// Returns the k'th smallest element of the treap in 1-based index, -1 on failure
  308.     inline int kth(int k){
  309.         if ((k < 1) || (k > size())) return -1;
  310.         node *l, *r, *cur = root;
  311.         for (; ;){
  312.             l = cur->l, r = cur->r;
  313.             if (l){
  314.                 if (k <= l->subtree) cur = l;
  315.                 else if ((l->subtree + 1) == k) return cur->key;
  316.                 else cur = r, k -= (l->subtree + 1);
  317.             }
  318.             else{
  319.                 if (k == 1) return (cur->key);
  320.                 else cur = r, k--;
  321.             }
  322.         }
  323.     }
  324.     /// Returns the count of keys less than x in the treap
  325.     inline int count(int key){
  326.         int res = 0;
  327.         node *l, *r, *cur = root;
  328.         while (cur){
  329.             l = cur->l, r = cur->r;
  330.             if (cur->key < key) res++;
  331.             if (key < cur->key) cur = l;
  332.             else{
  333.                 cur = r;
  334.                 if (l) res += l->subtree;
  335.             }
  336.         }
  337.         return res;
  338.     }
  339. };
  340.  
  341.  
  342.  
  343. /// Treap With Implicit Keys (Run Length Encoding)
  344. #define MAXN 1000010
  345. struct node{
  346.     node *l, *r;
  347.     int val, counter, mask, subtree, priority;
  348.     inline node(){
  349.         l = r = 0;
  350.     }
  351.     inline node(int v, int c, int p){
  352.         l = r = 0;
  353.         priority = p;
  354.         subtree = c, val = v, counter = c, mask = (1 << v);
  355.     }
  356.     inline node(int v, int c){
  357.         node(v, c, (rand() << 16) ^ rand());
  358.     }
  359.     inline void update(){
  360.         subtree = counter;
  361.         if (l) subtree += l->subtree;
  362.         if (r) subtree += r->subtree;
  363.     }
  364. } pool[MAXN]; /// Maximum number of nodes in treap
  365. struct Treap{
  366.     int idx;
  367.     struct node* root;
  368.     inline void join(node* cur){
  369.         if (!cur) return;
  370.         cur->update();
  371.         cur->mask = 1 << cur->val;
  372.         if (cur->l) cur->mask |= cur->l->mask;
  373.         if (cur->r) cur->mask |= cur->r->mask;
  374.     }
  375.     inline void merge(node* &cur, node* l, node* r){
  376.         if (!l || !r) cur = l ? l : r;
  377.         else if (l->priority > r->priority) merge(l->r, l->r, r), cur = l;
  378.         else merge(r->l, l, r->l), cur = r;
  379.         if (cur) join(cur);
  380.     }
  381.     /// Smallest v such that l->subtree = v and v >= key
  382.     inline void split(node* cur, node* &l, node* &r, int key, int counter = 0){
  383.         if (!cur){
  384.             l = r = 0;
  385.             return;
  386.         }
  387.         int cur_key = counter + (cur->l ? cur->l->subtree : 0);
  388.         if (key <= cur_key) split(cur->l, l, cur->l, key, counter), r = cur;
  389.         else split(cur->r, cur->r, r, key, cur_key + cur->counter), l = cur;
  390.         if (cur) join(cur);
  391.     }
  392.     inline void divide(node* &cur, int i){
  393.         node *l, *r, *m, *t;
  394.         split(cur, l, r, i);
  395.         if (!(!l || l->subtree == i)){
  396.             m = l;
  397.             while (m->r) m = m->r;
  398.             int v = m->val, c1 = i - (l->subtree - m->counter), c2 = m->counter - c1;
  399.             split(l, l, t, l->subtree - m->counter);
  400.             pool[idx] = node(v, c1);
  401.             merge(l, l, &pool[idx++]); /// Assign to t or m if required
  402.             pool[idx] = node(v, c2);
  403.             merge(l, l, &pool[idx++]); /// Assign to t or m if required
  404.         }
  405.         merge(cur, l, r);
  406.     }
  407.     inline void insert(int i, int v, int c){ /// Inserts c copies of v after position i
  408.         divide(root, i);
  409.         node *l, *r, *m;
  410.         split(root, l, r, i);
  411.         pool[idx] = node(v, c);
  412.         merge(l, l, &pool[idx++]);
  413.         merge(root, l, r);
  414.     }
  415.     inline void erase(int a, int b){ /// Removes the segment [a:b]
  416.         node *l, *r, *m;
  417.         divide(root, a - 1);
  418.         split(root, l, r, a - 1);
  419.         divide(r, b - a + 1);
  420.         split(r, m, r, b - a + 1);
  421.         merge(root, l, r);
  422.     }
  423.     inline int query(int a, int b){ /// Number of distinct characters(a-z) in the segment [a:b]
  424.         node *l, *r, *m;
  425.         divide(root, a - 1);
  426.         split(root, l, r, a - 1);
  427.         divide(r, b - a + 1);
  428.         split(r, m, r, b - a + 1);
  429.         int res = m->mask;
  430.         merge(l, l, m);
  431.         merge(root, l, r);
  432.         return __builtin_popcount(res);
  433.     }
  434.     Treap(){
  435.         idx = 0, root = 0;
  436.     }
  437.     inline int size(){
  438.         if (root) return root->subtree;
  439.         return 0;
  440.     }
  441. };
  442.  
  443.  
  444.  
  445. /// Walsh-Hadamard Transformation
  446. #define MAX 1048576
  447. long long ar[MAX];
  448. void walsh_transform(long long* ar, int n){
  449.     if (n == 0) return;
  450.     int i, m = n / 2;
  451.     walsh_transform(ar, m);
  452.     walsh_transform(ar + m, m);
  453.     for (i = 0; i < m; i++){
  454.         long long x = ar[i], y = ar[i + m];
  455.         ar[i] = x + y, ar[i + m] = x - y;
  456.     }
  457. }
  458. void inverse_walsh_transform(long long* ar, int n){
  459.     if (n == 0) return;
  460.     int i, m = n / 2;
  461.     inverse_walsh_transform(ar, m);
  462.     inverse_walsh_transform(ar + m, m);
  463.     for (i = 0; i < m; i++){
  464.         long long x = ar[i], y = ar[i + m];
  465.         ar[i] = (x + y) >> 1, ar[i + m] = (x - y) >> 1;
  466.     }
  467. }
  468. int main(){
  469.     int n, i, j, k, x;
  470.     scanf("%d", &n);
  471.     while (n--){
  472.         scanf("%d", &x);
  473.         ar[x]++;
  474.     }
  475.     walsh_transform(ar, MAX);
  476.     for (i = 0; i < MAX; i++) ar[i] *= ar[i];
  477.     inverse_walsh_transform(ar, MAX);
  478.     long long res = 0;
  479.     for (i = 0; i < MAX; i++) res += (ar[i] * i);
  480.     printf("%lld\n", res / 2);
  481.     return 0;
  482. }
  483.  
  484.  
  485.  
  486. /// 3D fenwick tree
  487. #define MAX 205
  488. /// 3D Fenwick tree, Range updates and point queries
  489. struct Fenwick3D{
  490.     int n, m, r, tree[MAX][MAX][MAX];
  491.     Fenwick3D(){
  492.     }
  493.     Fenwick3D(int a, int b, int c){
  494.         clr(tree);
  495.         n = a, m = b, r = c;
  496.     }
  497.     /// Add v to the cube from lower-right [i,j,k] to upper-left [1,1,1]
  498.     void update(int i, int j, int k, int v){
  499.         if ((i < 0) || (j < 0) || (i > n) || (j > m) || (k < 0) || (k > r)) return;
  500.         while (i){
  501.             int x = j;
  502.             while (x){
  503.                 int y = k;
  504.                 while (y){
  505.                     tree[i][x][y] += v;
  506.                     y ^= (y & (-y));
  507.                 }
  508.                 x ^= (x & (-x));
  509.             }
  510.             i ^= (i & (-i));
  511.         }
  512.     }
  513.     /// Add v to the cube from upper-left [x1,y1,z1] to lower-right [x2,y2,z2]
  514.     void update(int x1, int y1, int z1, int x2, int y2, int z2){
  515.         update(x2, y2, z2, 1), update(x1 - 1, y1 - 1, z2, 1);
  516.         update(x1 - 1, y2, z1 - 1, 1), update(x2, y1 - 1, z1 - 1, 1);
  517.         update(x1 - 1, y2, z2, -1), update(x2, y1 - 1, z2, -1);
  518.         update(x2, y2, z1 - 1, -1), update(x1 - 1, y1 - 1, z1 - 1, -1);
  519.     }
  520.     /// Query for the value at index [i][j][k]
  521.     int query(int i, int j, int k){
  522.         int res = 0;
  523.         while (i <= n){
  524.             int x = j;
  525.             while (x <= m){
  526.                 int y = k;
  527.                 while (y <= r){
  528.                     res += tree[i][x][y];
  529.                     y += (y & (-y));
  530.                 }
  531.                 x += (x & (-x));
  532.             }
  533.             i += (i & (-i));
  534.         }
  535.         return res;
  536.     }
  537. };
  538.  
  539.  
  540.  
  541. /// 2D Fenwick tree
  542. #define MAX 1010
  543. /// 2D Fenwick tree, Point updates and range queries
  544. class Fenwick2D{
  545.     public:
  546.     int n, m, tree[MAX][MAX];
  547.     Fenwick2D(){
  548.     }
  549.     Fenwick2D(int a, int b){
  550.         clr(tree);
  551.         n = a, m = b;
  552.     }
  553.     /// Add v to ar[i][j]
  554.     void update(int i, int j, int v){
  555.         while (i <= n){
  556.             int k = j;
  557.             while (k <= m){
  558.                 tree[i][k] += v;
  559.                 k += (k & (-k));
  560.             }
  561.             i += (i & (-i));
  562.         }
  563.     }
  564.     /// Query for sum of the sub-rectangle from upper-left [i,j] to lower-right [n,n]
  565.     int query(int i, int j){
  566.         if ((i < 0) || (j < 0) || (i > n) || (j > m)) return 0;
  567.         int res = 0;
  568.         while (i){
  569.             int k = j;
  570.             while (k){
  571.                 res += tree[i][k];
  572.                 k ^= (k & (-k));
  573.             }
  574.             i ^= (i & (-i));
  575.         }
  576.         return res;
  577.     }
  578.     /// Query for sum of the sub-rectangle from upper-left [i,j] to lower-right [k,l]
  579.     int query(int i, int j, int k, int l){
  580.         if (i > k || j > l) return 0;
  581.         int res = query(k, l) - query(i - 1, l) + query(i - 1, j - 1) - query(k, j - 1);
  582.         return res;
  583.     }
  584. };
  585. /// 2D Fenwick tree, Range updates and point queries
  586. class Fenwick2D{
  587.     public:
  588.     int n, m, tree[MAX][MAX];
  589.     Fenwick2D(){
  590.     }
  591.     Fenwick2D(int a, int b){
  592.         clr(tree);
  593.         n = a, m = b;
  594.     }
  595.     /// Add v to the sub-rectangle from upper-left [i,j] to lower-right [n,n]
  596.     void update(int i, int j, int v){
  597.         if ((i < 0) || (j < 0) || (i > n) || (j > m)) return;
  598.         while (i <= n){
  599.             int k = j;
  600.             while (k <= m){
  601.                 tree[i][k] += v;
  602.                 k += (k & (-k));
  603.             }
  604.             i += (i & (-i));
  605.         }
  606.     }
  607.     /// Add v to the sub-rectangle from upper-left [i,j] to lower-right [k,l]
  608.     void update(int i, int j, int k, int l, int v){
  609.         if (i > k || j > l) return;
  610.         update(i, j, v);
  611.         update(k + 1, j, -v);
  612.         update(k + 1, l + 1, v);
  613.         update(i, l + 1, -v);
  614.     }
  615.     /// Query for the value at index [i][j]
  616.     int query(int i, int j){
  617.         int res = 0;
  618.         while (i){
  619.             int k = j;
  620.             while (k){
  621.                 res += tree[i][k];
  622.                 k ^= (k & (-k));
  623.             }
  624.             i ^= (i & (-i));
  625.         }
  626.         return res;
  627.     }
  628. };
  629. /// 2D Fenwick tree, Range updates and range queries
  630. class Fenwick2D{
  631.     public:
  632.     int n, m;
  633.     long long tree[4][MAX][MAX];
  634.     Fenwick2D(){
  635.     }
  636.     Fenwick2D(int a, int b){
  637.         clr(tree);
  638.         n = a, m = b;
  639.     }
  640.     /// Add v to the sub-rectangle from upper-left [p,q] to lower-right [n,n]
  641.     void update(int p, int q, long long v){
  642.         if ((p < 0) || (q < 0) || (p > n) || (q > m)) return;
  643.         int i = p, c = p - 1, d = q - 1;
  644.         while (i <= n){
  645.             int j = q;
  646.             while (j <= m){
  647.                 tree[0][i][j] += v;
  648.                 tree[1][i][j] += (v * d);
  649.                 tree[2][i][j] += (v * c);
  650.                 tree[3][i][j] += (v * c * d);
  651.                 j += (j & (-j));
  652.             }
  653.             i += (i & (-i));
  654.         }
  655.     }
  656.     /// Query for sum of the sub-rectangle from upper-left [p,q] to lower-right [n,n]
  657.     long long query(int p, int q){
  658.         int i, j;
  659.         long long x, y, z, c, d, res;
  660.         i = p, x = y = z = 0;
  661.         while (i){
  662.             j = q, c = d = 0;
  663.             while (j){
  664.                 c += tree[0][i][j];
  665.                 d += tree[1][i][j];
  666.                 y += tree[2][i][j];
  667.                 z += tree[3][i][j];
  668.                 j ^= (j & (-j));
  669.             }
  670.             i ^= (i & (-i));
  671.             x += ((c * q) - d);
  672.         }
  673.         res = (x * p) - (y * q) + z;
  674.         return res;
  675.     }
  676.     /// Add v to the sub-rectangle from upper-left [i,j] to lower-right [k,l]
  677.     void update(int i, int j, int k, int l, long long v){
  678.         update(i, j, v);
  679.         update(k + 1, j, -v);
  680.         update(k + 1, l + 1, v);
  681.         update(i, l + 1, -v);
  682.     }
  683.     /// Query for sum of the sub-rectangle from upper-left [i,j] to lower-right [k,l]
  684.     long long query(int i, int j, int k, int l){
  685.         if (i > k || j > l) return 0;
  686.         long long res = query(k, l) - query(i - 1, l) + query(i - 1, j - 1) - query(k, j - 1);
  687.         return res;
  688.     }
  689. };
  690.  
  691.  
  692.  
  693. /// 2D Fenwick Tree with HashMap
  694. /// When N = 10^5, runs in 0.8 seconds in codeforces server for random cases
  695. /// When N = 2 * 10^5, runs in 2.00 seconds in codeforces server for random cases
  696. #define MAX 200010
  697. #define HMOD 16777215
  698. int n, m, tree[HMOD + 71235];
  699. long long hashmap[HMOD + 71235];
  700. inline void add(int i, int j, int v){
  701.     long long h = (((long long)i * 1000003) + j) + 917921;
  702.     int k = h & HMOD;
  703.     while (hashmap[k] && hashmap[k] != h) k++;
  704.     hashmap[k] = h, tree[k] += v;
  705. }
  706. inline int find(int i, int j){
  707.     long long h = (((long long)i * 1000003) + j) + 917921;
  708.     int k = h & HMOD;
  709.     while (hashmap[k] && hashmap[k] != h) k++;
  710.     return (hashmap[k] ? tree[k] : 0);
  711. }
  712. /// Add v to ar[i][j]
  713. inline void update(int i, int j, int v){
  714.     while (i <= n){
  715.         int k = j;
  716.         while (k <= m){
  717.             add(i, k, v);
  718.             k += (k & (-k));
  719.         }
  720.         i += (i & (-i));
  721.     }
  722. }
  723. /// Query for sum of the sub-rectangle from upper-left [i,j] to lower-right [n,n]
  724. inline int query(int i, int j){
  725.     if ((i < 0) || (j < 0) || (i > n) || (j > m)) return 0;
  726.     int res = 0;
  727.     while (i){
  728.         int k = j;
  729.         while (k){
  730.             res += find(i, k);
  731.             k ^= (k & (-k));
  732.         }
  733.         i ^= (i & (-i));
  734.     }
  735.     return res;
  736. }
  737. /// Query for sum of the sub-rectangle from upper-left [i,j] to lower-right [k,l]
  738. inline int query(int i, int j, int k, int l){
  739.     if (i > k || j > l) return 0;
  740.     int res = query(k, l) - query(i - 1, l) + query(i - 1, j - 1) - query(k, j - 1);
  741.     return res;
  742. }
  743. int main(){
  744.     clock_t start = clock();
  745.     int q, i, j, k, l, x, y, z;
  746.     n = 200000;
  747.     m = n, q = n;
  748.     long long res = 0;
  749.     while (q--){
  750.         int flag = ran(0, 1);
  751.         if (flag == 0){
  752.             i = ran(1, n), k = ran(i, n);
  753.             j = ran(1, m), l = ran(j, m);
  754.             res += query(i, j, k, l);
  755.         }
  756.         if (flag == 1){
  757.             i = ran(1, n), j = ran(1, m), x = ran(1, 100);
  758.             update(i, j, x);
  759.         }
  760.     }
  761.     printf("%0.5f\n", (clock() - start) / (1.0 * CLOCKS_PER_SEC));
  762.     return 0;
  763. }
  764.  
  765.  
  766.  
  767. /// DSU on subtree
  768. /// Codeforces 601D
  769. /// D[i] = number of distinct strings starting at vertex i and ending on some vertex down subtree i
  770. #define MAX 300010
  771. const long long HMOD[] = {2078526727, 2117566807};
  772. const long long BASE[] = {1572872831, 1971536491};
  773. char str[MAX];
  774. vector <int> adj[MAX];
  775. int n, C[MAX], D[MAX], T[MAX];
  776. set <long long> S[MAX];
  777. void dfs(int i, int p, long long h1, long long h2){ /// hash = 400687
  778.     h1 = (h1 * BASE[0] + str[i - 1] + 10007) % HMOD[0];
  779.     h2 = (h2 * BASE[1] + str[i - 1] + 10007) % HMOD[1];
  780.     int j, k, x, idx = 0, res = 0, len = adj[i].size();
  781.     for (j = 0; j < len; j++){
  782.         x = adj[i][j];
  783.         if (x != p){
  784.             dfs(x, i, h1, h2);
  785.             if (D[x] > res) res = D[x], idx = x; /// update
  786.         }
  787.     }
  788.     if (idx) T[i] = T[idx]; /// If maximum subtree child found, set root to root of subtree
  789.     for (j = 0; j < len; j++){
  790.         x = adj[i][j];
  791.         if (x != p && T[x] != T[i]){
  792.             for (auto it: S[T[x]]) S[T[i]].insert(it); /// If not parent and not maximum subtree, insert
  793.             S[T[x]].clear(); /// Finally clear the remaining items since not required anymore
  794.         }
  795.     }
  796.     S[T[i]].insert((h1 << 31) ^ h2);
  797.     D[i] = S[T[i]].size();
  798. }
  799. int main(){
  800.     int i, j, k, l, a, b, c, x, res;
  801.     scanf("%d", &n);
  802.     for (i = 1; i <= n; i++) T[i] = i;
  803.     for (i = 1; i <= n; i++) scanf("%d", &C[i]); /// Set parent[i] = i
  804.     scanf("%s", str);
  805.     for (i = 1; i < n; i++){
  806.         scanf("%d %d", &a, &b);
  807.         adj[a].push_back(b);
  808.         adj[b].push_back(a);
  809.     }
  810.     dfs(1, 0, 0, 0);
  811.     for (res = 0, c = 0, i = 1; i <= n; i++){
  812.         x = C[i] + D[i];
  813.         if (x > res) res = x, c = 1;
  814.         else if (x == res) c++;
  815.     }
  816.     printf("%d\n%d\n", res, c);
  817.     return 0;
  818. }
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!