fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
  3. #define FORD(i,b,a) for (int i=(b),_a=(a);i>=_a;i=i-1)
  4. #define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
  5. #define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
  6. #define ALL(v) (v).begin(),(v).end()
  7. #define fi   first
  8. #define se   second
  9. #define MASK(i) (1LL<<(i))
  10. #define BIT(x,i) (((x)>>(i))&1)
  11. #define div   ___div
  12. #define next   ___next
  13. #define prev   ___prev
  14. #define left   ___left
  15. #define right   ___right
  16. #define __builtin_popcount __builtin_popcountll
  17. using namespace std;
  18. template<class X,class Y>
  19.     void minimize(X &x,const Y &y) {
  20.         if (x>y) x=y;
  21.     }
  22. template<class X,class Y>
  23.     void maximize(X &x,const Y &y) {
  24.         if (x<y) x=y;
  25.     }
  26. template<class T>
  27.     T Abs(const T &x) {
  28.         return (x<0?-x:x);
  29.     }
  30.  
  31. /* Author: Van Hanh Pham */
  32.  
  33. /** END OF TEMPLATE - ACTUAL SOLUTION COMES HERE **/
  34.  
  35. class FenwickTree {
  36. private:
  37.     int n;
  38.     vector<int> v;
  39.  
  40. public:
  41.     FenwickTree(int n = 0) {
  42.         this->n = n;
  43.         v.assign(n + 7, 0);
  44.     }
  45.  
  46.     void update(int x, int d) {
  47.         if (x == 0) return;
  48.         for (; x <= n; x += x & -x) v[x] += d;
  49.     }
  50.  
  51.     int get(int x) const {
  52.         int res = 0;
  53.         for (; x >= 1; x &= x - 1) res += v[x];
  54.         return res;
  55.     }
  56.  
  57.     int getSum(int l, int r) const {
  58.         return l == 1 ? get(r) : get(r) - get(l - 1);
  59.     }
  60. };
  61.  
  62. struct Node {
  63.     Node *child[26];
  64.     int last;
  65.  
  66.     Node() {
  67.         REP(i, 26) child[i] = NULL;
  68.         last = 0;
  69.     }
  70. };
  71.  
  72. #define MAX   200200
  73.  
  74. int numWord, numQuery;
  75. string words[MAX];
  76. Node *prefixRoot, *suffixRoot;
  77. vector<pair<int, int> > queryAt[MAX];
  78. long long answer[MAX];
  79.  
  80. void init(void) {
  81.     cin >> numWord >> numQuery;
  82.     FOR(i, 1, numWord) cin >> words[i];
  83.     FOR(i, 1, numQuery) {
  84.         int l, r; cin >> l >> r;
  85.         queryAt[r].push_back(make_pair(l, i));
  86.     }
  87. }
  88.  
  89. void addString(Node *root, const string &s) {
  90.     Node *p = root;
  91.  
  92.     FORE(it, s) {
  93.         if (p->child[*it - 'a'] == NULL) p->child[*it - 'a'] = new Node();
  94.         p = p->child[*it - 'a'];
  95.     }
  96. }
  97.  
  98. void prepare(void) {
  99.     prefixRoot = new Node();
  100.     suffixRoot = new Node();
  101.  
  102.     FOR(i, 1, numWord) {
  103.         addString(prefixRoot, words[i]);
  104.         reverse(ALL(words[i]));
  105.         addString(suffixRoot, words[i]);
  106.         reverse(ALL(words[i]));
  107.     }
  108. }
  109.  
  110. void process(void) {
  111.     FenwickTree prefixBit[26], suffixBit[26], allSuffixBit;
  112.  
  113.     REP(i, 26) {
  114.         prefixBit[i] = FenwickTree(numWord);
  115.         suffixBit[i] = FenwickTree(numWord);
  116.     }
  117.     allSuffixBit = FenwickTree(numWord);
  118.  
  119.     FOR(i, 1, numWord) {
  120.         Node *p = prefixRoot;
  121.         FORE(it, words[i]) {
  122.             p = p->child[*it - 'a'];
  123.             if (it != words[i].begin()) prefixBit[*it - 'a'].update(p->last, -1);
  124.             p->last = i;
  125.             if (it != words[i].begin()) prefixBit[*it - 'a'].update(p->last, 1);
  126.         }
  127.  
  128.         reverse(ALL(words[i]));
  129.  
  130.         p = suffixRoot;
  131.         FORE(it, words[i]) {
  132.             p = p->child[*it - 'a'];
  133.             allSuffixBit.update(p->last, -1);
  134.             if (it != words[i].begin()) suffixBit[*it - 'a'].update(p->last, -1);
  135.             p->last = i;
  136.             allSuffixBit.update(p->last, 1);
  137.             if (it != words[i].begin()) suffixBit[*it - 'a'].update(p->last, 1);
  138.         }
  139.  
  140.         reverse(ALL(words[i]));
  141.  
  142.         FORE(jt, queryAt[i]) {
  143.             int l = jt->fi, r = i, id = jt->se;
  144.             REP(k, 26) {
  145.                 if (prefixRoot->child[k] != NULL && prefixRoot->child[k]->last >= l)
  146.                     answer[id] += allSuffixBit.getSum(l, r);
  147.                 int numPre = prefixBit[k].getSum(l, r);
  148.                 int numSuf = allSuffixBit.getSum(l, r) - suffixBit[k].getSum(l, r);
  149.                 answer[id] += 1LL * numPre * numSuf;
  150.             }
  151.         }
  152.     }
  153.  
  154.     FOR(i, 1, numQuery) cout << answer[i] << "\n";
  155. }
  156.  
  157. int main(void) {
  158. #ifdef SKY
  159.     freopen("tmp.txt", "r", stdin);
  160. #endif // SKY
  161.  
  162.     init();
  163.     prepare();
  164.     process();
  165.     return 0;
  166. }
  167.  
  168.  
  169. /*** LOOK AT MY CODE. MY CODE IS AMAZING :D ***/
  170.  
Success #stdin #stdout 0.01s 15088KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/4Xhvko
language:
C++ 4.3.2 (gcc-4.3.2)
created:
5 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!