API tools faq
paste
Advertisement
sleepy_coder

very long template

sleepy_coder
Oct 23rd, 2019
121
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 12.42 KB | None | 0 0
raw download clone embed print report
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. using namespace std;
  4. using namespace __gnu_pbds;
  5.  
  6. using ll=long long; using ld=long double; using vi=vector<int>; using vl=vector<ll>; using vs=vector<string>;
  7. using pii=pair<int, int>;  using vii=vector<pii>; using pll=pair<ll, ll>; using vll=vector<pll>;
  8. using mii=map<int, int>; using mll=map<ll, ll>; using msi=map<string, ll>; using vvi=vector< vi >;
  9. template <typename T> using ordered_set=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  10. /*const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
  11. struct chash {
  12.     int operator()(int x) const { return x ^ RANDOM; }
  13. };
  14. gp_hash_table<int, int, chash> table; */
  15.  
  16. #define     endl               "\n"
  17. #define     inf                (1<<30)
  18. #define     eps                (1e-9)
  19. #define     mod                (1000000007)
  20. #define     pi                 (acos(-1.0))
  21. #define     fast_io            ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  22. #define     _unique(c)         (c).resize(unique(begin(c), end(c)) - (c).begin());
  23. #define     debug(x)           cerr <<"Line "<< __LINE__ <<" : "<< #x " = "<< x <<endl;
  24. #define     rep(i, n)          for(__typeof(n) i=0; i<(n); i++)
  25. #define     foab(i, a, b)      for(__typeof(b) i=(a); i<=(b); i++)
  26. #define     foba(i, a, b)      for(__typeof(b) i=(b); i>=(a); i--)
  27. #define     forit(it, l)       for(__typeof((l).begin()) it = begin(l); it != end(l); it++)
  28. #define     file_io            freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
  29. #define     error(args...) {                                                             \
  30.                 string _s = #args; replace(_s.begin(), _s.end(), ',', ' ');              \
  31.                 stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); \
  32.             }
  33. void err(istream_iterator<string> it) {}                 template <typename T, typename... Args>
  34. void err(istream_iterator<string> it, T a, Args... args) { cerr<<*it<<" = "<<a<<endl; err(++it, args...); }
  35.  
  36. template<typename T, typename TT>
  37. ostream& operator<<(ostream &os, const pair< T, TT > &t) { return os << "(" << t.first << "," << t.second << ")"; }
  38. template<typename T, typename TT, typename TTT>
  39. ostream& operator<<(ostream &os, const tuple< T, TT, TTT > &t) { return os << "(" << get<0>(t) << "," << get<1>(t) << "," << get<2>(t) << ")"; }
  40. template<typename T>
  41. ostream& operator<<(ostream& os, const vector<T> &t) { ll n = t.size(); rep(i, n) os << t[i] << " "; return os; }
  42.  
  43. enum COLOR{ white = 1 , grey = 2 , black = 3, red = 4, green = 5, blue = 6 };
  44.  
  45.  
  46.  
  47.  
  48.  
  49. namespace UtilSpace {
  50.  
  51.     vii dir_4 { {1,0}, {0,1}, {-1,0}, {0,-1} };
  52.     vii dir_8 { {0,1}, {1,1}, {1,0}, {1,-1}, {0,-1}, {-1,-1}, {-1,0}, {-1,1} };
  53.     vii dir_knight { {2,1}, {1,2}, {-1,2}, {-2,1}, {-2,-1}, {-1,-2}, {1,-2}, {2,-1} };
  54.  
  55.     bool checkBit(int n, int pos) { return (n & (1<<pos)) != 0; }
  56.     int setBit(int n, int pos) {return (n | (1<<(pos))); }
  57.     int resetBit(int n, int pos) { return (n & ~(1 << pos)); }
  58.     void printBits(int n){ if(n >= 2)printBits(n/2); cout<<(n&1); }
  59.     int countOnes(int n) { int r=0; while(n && ++r) n -= n & -n; return r; }
  60.     bool isPowerOfTwo(int n) { return n && !(n & (n - 1)); }
  61.  
  62.     template <typename T>
  63.     string toString(T n) { stringstream ss; ss << n; return ss.str(); }
  64.  
  65.     ll bigMul(ll a,ll b,ll m) {
  66.         ll result = 0; a %= m;
  67.         while(b) { if(b&1LL) result=(result+a)%m; a=(a+a)%m; b>>=1LL; }
  68.         return result;
  69.     }
  70.     //using bigMul(a, b, m) makes it slow.....!!!
  71.     ll bigMod(ll b, ll e, ll m) {
  72.         ll res = 1LL%m; b %= m;
  73.         while(e) {
  74.             if(e & 1LL) res = bigMul(res, b, m); // check the ith bit
  75.             e >>= 1LL; // move the (i+1)th bit at pos 0
  76.             b = bigMul(b, b, m); // b = b^(2^(i+1))
  77.         }
  78.         return res;
  79.     }
  80.  
  81.     ll bigPow(ll a, ll b) {
  82.         ll res = 1LL;
  83.         while(b) { res = (b&1LL)? res*a : res, b >>= 1LL, a *= a; }
  84.         return res;
  85.     }
  86.  
  87.     template< typename T >
  88.     T exEuclid(T a, T b, T& x, T& y) {
  89.         if(!b){ x = 1, y = 0; return a; }
  90.         T x1, y1, temp = exEuclid<T>(b, a%b, x1, y1);
  91.         x = y1, y = x1 - y1*(a/b);
  92.         return temp;
  93.     }
  94.  
  95.     template< typename T >
  96.     T modInverse(T a, T m) {
  97.         T x, y; T g = exEuclid<T>(a, m, x, y);
  98.         if(g != 1){ return -1; } // does not exists
  99.         else{ return (x%m + m)%m; }
  100.     }
  101.  
  102.  
  103.  
  104.     const unsigned int M = 2e8+2; // increadible memory consuming
  105.  
  106.     int status[(M>>6) + 7] = {0};
  107.     bitset<500000002> _primalStatus; // increadible memory consuming
  108.     #define on(x) (status[x>>6] & (1<<((x&63)/2)))
  109.     #define mark(x)  status[x>>6] |= (1<<((x&63)/2))
  110.  
  111.     //you can call it anywhere...TESTED
  112.     vector<int> sieve(const int& range) {
  113.         fill(status, status + (range>>6) + 7, 0);//clear the markings
  114.         vector<int> primes;
  115.         if(range >= 2) primes.push_back(2); // 2 is a prime
  116.         int i(3);
  117.         for(; i*i <= range; i += 2)  // have to check primes up to (sqrt(N))
  118.             if(!on(i)) { // so, i is a prime, so, discard all the multiples
  119.                 primes.push_back(i); // insert the prime
  120.                 for(int j = i*i ; j <= range; j += i + i)  // j = i * i, because it’s the first number to be colored
  121.                     mark(j);   // status of the multiple is 1
  122.             }
  123.         for(; i <= range; i += 2) if(!on(i)) primes.push_back(i); // push primes greater than sqrt(range)
  124.         return primes;
  125.     }
  126.     //you must call sieve() once before calling it...TESTED
  127.     inline bool isPrime(const int& n) { return n == 2 || (n > 2 && (n&1) && !on(n)); }
  128.  
  129.     // TESTED each time calls sieve() ... can be modified
  130.     vector<ll> segmentedSieve(const ll& a, const ll& b) {
  131.         int x = floor(sqrt(b*1.0)) + 1;
  132.         vector<int> rootedPrimes = sieve(x);
  133.         const int range(b - a + 1);
  134.         _primalStatus.reset();
  135.  
  136.         for (int& curPrime : rootedPrimes) {
  137.             if(curPrime == 2) continue; // this is a tricky case
  138.             // Start should be the max(curPrime^2, first multiple of curPrime >= a)
  139.             ll start = max((curPrime * curPrime * 1LL), (((a + curPrime - 1LL) / curPrime) * curPrime));
  140.             start = (start & 1LL)? start : start + curPrime; // make sure start is odd.
  141.             for (int i = start - a; i < range; i += curPrime<<1LL) {
  142.                 _primalStatus.set(i>>1);
  143.             }
  144.         }
  145.         vl segPrimes;
  146.         if (a <= 2 && b >= 2) { segPrimes.push_back(2LL); }
  147.         for (int k = (a & 1) ? 0 : 1; k < range; k += 2) {
  148.             if (!_primalStatus.test(k>>1) && a+k != 1) {
  149.                 segPrimes.push_back((ll)a+k);
  150.             }
  151.         }
  152.         return segPrimes;
  153.     }
  154.  
  155.     bool isSegmentedPrime(const ll& n, const ll& l, const ll& r) {
  156.         return n>=l && n<=r && (n==2 || (n>2 && (n&1LL) && !_primalStatus.test((n-l)>>1LL)));
  157.     }
  158.  
  159.     // TESTED each time calls sieve() ... can be modified
  160.     // generate primes upto 10^9 in about 4 second
  161.     vector<int> segmentedSieve(const int& n) {
  162.         int x = floor(sqrt(n))+1;
  163.         vector<int> rootedPrimes = sieve(x), primes;
  164.         for(auto & p : rootedPrimes) if(p*p<=n)primes.push_back(p);
  165.         int a = x, b = 2*x; // sqrt decompose the upper part of sqrt(n)
  166.         bitset<16000> ps;
  167.         while(a < n) {
  168.             ps.reset();
  169.             b = b >= n ? n : b; // adjust b
  170.             const int range(b - a + 1);
  171.             for (int& curPrime : rootedPrimes) {
  172.                 if(curPrime == 2) continue; // this is a tricky case
  173.                 // Start should be the max(curPrime^2, first multiple of curPrime >= a)
  174.                 ll start = max((curPrime * curPrime * 1LL), (((a + curPrime - 1LL) / curPrime) * curPrime));
  175.                 start = (start & 1LL)? start : start + curPrime; // make sure start is odd.
  176.                 for (int i = start - a; i < range; i += curPrime<<1LL) {
  177.                     ps.set(i>>1);
  178.                 }
  179.             }
  180.             if (a <= 2 && b >= 2) { primes.push_back(2LL); }
  181.             for (int k = (a & 1) ? 0 : 1; k < range; k += 2) {
  182.                 if (!ps.test(k>>1) && a+k != 1) {
  183.                     primes.push_back((ll)a+k);
  184.                 }
  185.             }
  186.             a += x, b += x;
  187.         }
  188.         return primes;
  189.     }
  190.  
  191.  
  192.     //sieve must be called externally with suitable limit..TESTED
  193.     // factorsWithCount, factorSum, factorCount
  194.     tuple<vll, ll, ll> primeFactorize(const ll& num, const vi& rootedPrimes) {
  195.         ll n = num, factorSum = 1, factorCount = 1;
  196.         vll factorsWithCount;
  197.         for(const int& smallPrime : rootedPrimes) {
  198.             if(smallPrime * smallPrime * 1LL <= n && !(n % smallPrime)) {
  199.                 ll pc = 0;
  200.                 while(!(n % smallPrime)) { n /= smallPrime, ++pc; }
  201.                 factorsWithCount.emplace_back(smallPrime, pc);
  202.                 factorSum *= (bigPow(smallPrime, pc+1) - 1) / (smallPrime - 1LL); // extra
  203.                 factorCount *= (pc+1);  //extra
  204.             }
  205.         }
  206.         // if n remains then it must be a prime number > sqrt(initial_n)
  207.         if(n > 1) {
  208.            factorsWithCount.emplace_back(n, 1LL);
  209.            factorSum *= (bigPow(n, 2) - 1) / (n - 1LL); // extra
  210.            factorCount *= 2LL; // extra
  211.         }
  212.         return make_tuple(factorsWithCount, factorSum, factorCount);
  213.     }
  214.  
  215.     //--------------------------strings in hashland!-----------------------------
  216.  
  217.     // time Complexity O(str.size())
  218.     // rolling hash for lowercase chars made string with p = immediate next prime
  219.     ll computeHash(string const& str) {
  220.         const int p = 31; // this may vary
  221.         const int m = 1e9 + 9; // this may not vary
  222.         ll hash_value = 0LL, p_i = 1;
  223.         for(const char& c : str) {
  224.             hash_value = (hash_value + (c - 'a' + 1) * p_i) % m, p_i = (p_i * p)%m;
  225.         }
  226.         return hash_value;
  227.     }
  228.  
  229.     //sort according to hash and group ... O(nm + nlog(n))
  230.     vvi groupIdenticalStrings(vs const& strings) {
  231.         int n = strings.size();
  232.         vll hashes(n);
  233.         rep(i, n) hashes[i] = {computeHash(strings[i]), i}; // O(nm)
  234.         sort(hashes.begin(), hashes.end()); // O(nlog(n))
  235.         vvi groups;
  236.         rep(i, n) {
  237.             if(!i || hashes[i-1].first != hashes[i].first) groups.emplace_back();
  238.             groups.back().push_back(hashes[i].second);
  239.         }
  240.         return groups;
  241.     }
  242.  
  243.     //  the probability that collision happens is only ≈ 1 / m
  244.     // complexity: O(n + n*2log(n))
  245.     int countUniqueSubstrings(string const& str) {
  246.         int n = str.size();
  247.         const int p = 31, m = 1e9 + 9;
  248.         vl pow_p(n,1);
  249.         for(int i = 1; i < n; i++) pow_p[i] = (p * pow_p[i-1]) % m;
  250.         vl h(n+1, 0LL); // upto 0...n length prefix hash
  251.         foab(i, 1, n) h[i] = (h[i-1] + (str[i-1] - 'a' + 1) * pow_p[i-1]) % m; // prefix hashing
  252.         int cnt(0);
  253.         foab(len, 1, n) {
  254.             set<ll> hs;
  255.             foab(i, 0, n-len) {
  256.                 ll curHash = (h[i+1] + m - h[i]) % m;
  257.                 curHash = (curHash * pow_p[n-1-i]) % m; // make it p^n-1 * hash[i...j]
  258.                 hs.insert(curHash);
  259.             }
  260.             cnt += hs.size(); // add number of unique hashes of sunstrings of length len
  261.         }
  262.         return cnt;
  263.     }
  264.  
  265.     // linear time complexity...hashing based
  266.     vi patternMatch(string const& needle, string const& haystack) {
  267.         int l1 = needle.size(), l2 = haystack.size();
  268.         vi indices;
  269.         if(!l1 || l1 > l2)
  270.             return indices;
  271.         const int p = 31, m = 1e9+9;
  272.         vl power(l2, 1LL), prefixHash(l2+1, 0LL);
  273.         for(int i = 1 ; i <= l2; i++) {
  274.             if(i<l2) power[i] = (power[i-1] * p) % m; // power computing
  275.             prefixHash[i] = (prefixHash[i-1] + (haystack[i-1]-'a'+1) * power[i-1]) % m; // prefix hashing
  276.         }
  277.         ll needleHash = UtilSpace::computeHash(needle);
  278.         needleHash = (needleHash * power[l2-1]) % m;
  279.         for(int i = 0; i <= l2-l1; i++) {
  280.             ll curHash = (prefixHash[i+l1] + m - prefixHash[i]) % m;
  281.             curHash = (curHash * power[l2-1 - i]) % m; // make it p^n-1 * hash[i...j]
  282.             if(curHash == needleHash) indices.push_back(i);
  283.         }
  284.         return indices;
  285.     }
  286.  
  287.     //---------------------------Trie Data Structure (just implemented not tested at all)-------------------
  288.     struct RadixTree {
  289.         RadixTree() {
  290.             rootNode = new TrieNode();
  291.             pointer = rootNode;
  292.         }
  293.         bool insertWord(string const& word) {
  294.             pointer = rootNode;
  295.             for(const char& ch : word) {
  296.                 unsigned edgeID = (ch - base);
  297.                 if(!pointer->nextNodes[edgeID])
  298.                     pointer->nextNodes[edgeID] = new TrieNode();
  299.                 pointer = pointer->nextNodes[edgeID];
  300.             }
  301.             return pointer->endMark = true;
  302.         }
  303.  
  304.         bool containsWord(string const& word) {
  305.             pointer = rootNode;
  306.             for(char const& ch : word) {
  307.                 unsigned edgeID = ch - base;
  308.                 if(!pointer->nextNodes[edgeID]) return false;
  309.                 pointer = pointer->nextNodes[edgeID];
  310.             }
  311.             for(int i = 0; i < edgeWidth; i++) if(pointer->nextNodes[i]) return true;
  312.             return false;  
  313.         }
  314.  
  315.         void showSuggestions(string const& prefix) {
  316.             pointer = rootNode;
  317.             for(char const& ch: prefix) {
  318.                 unsigned edgeID = ch - base;
  319.                 if(!pointer->nextNodes[edgeID]) return;
  320.                 pointer = pointer->nextNodes[edgeID];
  321.             }
  322.             printUtil(pointer, prefix);
  323.         }
  324.  
  325.         void clearWords() {
  326.             deleteUtil(rootNode);
  327.             rootNode = new TrieNode();
  328.             pointer = rootNode;
  329.         }
  330.         ~RadixTree() {
  331.             pointer = rootNode;
  332.             deleteUtil(rootNode);
  333.             pointer = rootNode = NULL;
  334.         }
  335.  
  336.     private:
  337.         //----------you can change these things when needed----------------
  338.  
  339.         char base = '0';
  340.         unsigned edgeWidth = 10;
  341.        
  342.         struct TrieNode {
  343.             bool endMark;
  344.             struct TrieNode* nextNodes[10];
  345.             TrieNode() {
  346.                 endMark = false;
  347.                 for(int i = 0; i < 10; i++) nextNodes[i] = NULL;
  348.             }
  349.         } * rootNode, * pointer;
  350.  
  351.         //------okay, it'll be okay-------change size from 10 to different--------
  352.  
  353.         void printUtil(TrieNode* current, string message) {
  354.             if(current->endMark) cout << message << endl;
  355.             for(int i = 0; i < edgeWidth; i++) if(current->nextNodes[i]) {
  356.                 printUtil(current->nextNodes[i], message + (char)(base + i));
  357.             }
  358.            
  359.         }
  360.  
  361.         void deleteUtil(TrieNode* current) {
  362.             for(int i = 0; i < edgeWidth; i++) if(current->nextNodes[i]) {
  363.                 deleteUtil(current->nextNodes[i]);
  364.             }
  365.             delete current;
  366.         }
  367.     };
  368.     //-------------- ---Mo's Algorithm (without update i.e. : only query using block decomposition)-------------
  369.  
  370.     struct MoQuery {
  371.         struct Query {
  372.             int l, r, id, k;
  373.             bool operator<(const Query& rhs) {
  374.             int block_a = l / k, block_b = rhs.l / k;
  375.             return (block_a == block_b) ? (r < rhs.r) : (block_a < block_b);
  376.         }
  377.         } * q;
  378.  
  379.         int l, r, maxn, block_size, *a;
  380.         ll sum, *ans;
  381.         ///int distinct = 0;
  382.        
  383.         //step 1
  384.         MoQuery(int *ara, int query_no) {
  385.             l = 0, r = -1, sum = 0;    
  386.             a = ara;
  387.             maxn = query_no;
  388.             block_size = sqrt(maxn);
  389.             q = new Query[maxn];
  390.             for(int i = 0 ; i < maxn; i++) q[i].k = block_size;
  391.             ans = new long long[maxn];
  392.         }
  393.  
  394.         ///unordered_map<int , int> cnt;
  395.  
  396.         //adjust it
  397.         void add(const int& indx) {
  398.             sum += a[indx];
  399.         }
  400.         //adjust it
  401.         void remove(const int& indx) {
  402.             sum -= a[indx];
  403.         }
  404.         //step 2...
  405.         void pushQuery(int const& l, int const& r, int const& indx) { q[indx].l = l, q[indx].r = r, q[indx].id = indx; }
  406.         //step 3
  407.         void processQueries() {
  408.             sort(q, q + maxn);
  409.             for(int i = 0; i < maxn; i++) {
  410.                 while(l > q[i].l) add(--l);
  411.                 while(r < q[i].r) add(++r);
  412.                 while(l < q[i].l) remove(l++);
  413.                 while(r > q[i].r) remove(r--);
  414.                 ans[q[i].id] = sum;
  415.             }
  416.         }
  417.  
  418.         ~MoQuery() {
  419.             delete [] q; q = NULL;
  420.             delete [] ans; ans = NULL;
  421.         }
  422.     };
  423.     //--------------------------------
  424.  
  425. };
  426.  
  427. //============== ================================= long template ================ ==================== ===========================//
  428.  
  429.  
  430.  
  431.  
  432.  
  433. int main(int argc, char** argv) {
  434. #ifdef LOCAL
  435.     file_io
  436. #endif
  437.     fast_io
  438.    
  439.     //------------------------------------------------
  440.  
  441.    
  442.    
  443.  
  444.  
  445.        
  446.     //------------------------------------------------ 
  447.    
  448.     return 0;
  449. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
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!