fork(1) download
copy 
  1.     /*
  2.     Author: Ishmeet Dosanjh
  3.     Date of Created: 1/12/17
  4.     Version: 0.1 
  5.     */
  6.  
  7.     #pragma comment(linker, "/stack:20000000")
  8.     #pragma GCC optimize("Ofast")
  9.     #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  10.  
  11.     #define _CRT_SECURE_NO_WARNINGS
  12.     #include  <climits>
  13.     # include <iostream>
  14.     # include <cmath>
  15.     # include <algorithm>
  16.     # include <stdio.h>
  17.     # include <cstdint>
  18.     # include <cstring>
  19.     # include <string>
  20.     # include <cstdlib>
  21.     # include <vector>
  22.     # include <bitset>
  23.     # include <map>
  24.     # include <queue>
  25.     # include <ctime>
  26.     # include <stack>
  27.     # include <set>
  28.     # include <list>
  29.     # include <random>
  30.     # include <deque>
  31.     # include <functional>
  32.     # include <iomanip>
  33.     # include <sstream>
  34.     # include <fstream>
  35.     # include <complex>
  36.     # include <numeric>
  37.     # include <immintrin.h>
  38.     # include <cassert>
  39.     # include <array>
  40.     # include <tuple>
  41.     // #include <unordered_set> i ngcc 6.6
  42.     using namespace std;
  43.  
  44.     // Let's define unordered map
  45.     # ifdef __GNUC__
  46.     # if __cplusplus > 199711L
  47.     # include <unordered_set>
  48.     # include <unordered_map>
  49.     # else
  50.     # include <tr1/unordered_map>
  51.     # include <tr1/unordered_set>
  52.     using namespace tr1;
  53.     # endif
  54.     # else
  55.     # include <unordered_map>
  56.     # include <unordered_set>
  57.     # endif
  58.  
  59.     #define VA_NUM_ARGS(...) VA_NUM_ARGS_IMPL_((0,__VA_ARGS__, 6,5,4,3,2,1))
  60.     #define VA_NUM_ARGS_IMPL_(tuple) VA_NUM_ARGS_IMPL tuple
  61.     #define VA_NUM_ARGS_IMPL(_0,_1,_2,_3,_4,_5,_6,N,...) N
  62.     #define macro_dispatcher(macro, ...) macro_dispatcher_(macro, VA_NUM_ARGS(__VA_ARGS__))
  63.     #define macro_dispatcher_(macro, nargs) macro_dispatcher__(macro, nargs)
  64.     #define macro_dispatcher__(macro, nargs) macro_dispatcher___(macro, nargs)
  65.     #define macro_dispatcher___(macro, nargs) macro ## nargs
  66.     #define DBN1(a)           cerr<<#a<<"="<<(a)<<"\n"
  67.     #define DBN2(a,b)         cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<"\n"
  68.     #define DBN3(a,b,c)       cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<"\n"
  69.     #define DBN4(a,b,c,d)     cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<"\n"
  70.     #define DBN5(a,b,c,d,e)   cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<"\n"
  71.     #define DBN6(a,b,c,d,e,f) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<", "<<#f<<"="<<(f)<<"\n"
  72.     #define DBN(...) macro_dispatcher(DBN, __VA_ARGS__)(__VA_ARGS__)
  73.     #define DA(a,n) cerr<<#a<<"=["; printarray(a,n); cerr<<"]\n"
  74.     #define DAR(a,n,s) cerr<<#a<<"["<<s<<"-"<<n-1<<"]=["; printarray(a,n,s); cerr<<"]\n"
  75.  
  76.     #ifdef _MSC_VER
  77.     #define PREFETCH(ptr, rw, level) ((void)0)
  78.     #else
  79.     #define PREFETCH(ptr, rw, level) __builtin_prefetch(ptr, rw, level)
  80.     #endif
  81.  
  82.     #ifdef LOCAL
  83.     #define CURTIME() cerr << clock() * 1.0 / CLOCKS_PER_SEC << endl
  84.     #else
  85.     #define CURTIME()
  86.     #endif
  87.     #define pb push_back
  88.     #define mp make_pair
  89.     typedef long long ll;
  90.     typedef unsigned int uint;
  91.     typedef unsigned long long ull;
  92.     typedef double d;
  93.     typedef float f;
  94.     typedef pair<int, int> pii;
  95.     typedef pair<long long, long long> pll;
  96.     typedef vector<int> vi;
  97.     typedef vector<long long> vll;
  98.     typedef int itn;
  99.     typedef long l;
  100.     /***************************************************************/
  101.     // TEMPLATE DECLARATIONS 
  102.     template<class T1, class T2, class T3>
  103.     struct triple{ T1 a; T2 b; T3 c; triple() : a(T1()), b(T2()), c(T3()) {}; triple(T1 _a, T2 _b, T3 _c) :a(_a), b(_b), c(_c){} };
  104.     template<class T1, class T2, class T3>
  105.     bool operator<(const triple<T1,T2,T3>&t1,const triple<T1,T2,T3>&t2){if(t1.a!=t2.a)return t1.a<t2.a;else if(t1.b!=t2.b)return t1.b<t2.b;else return t1.c<t2.c;}
  106.     template<class T1, class T2, class T3>
  107.     bool operator>(const triple<T1,T2,T3>&t1,const triple<T1,T2,T3>&t2){if(t1.a!=t2.a)return t1.a>t2.a;else if(t1.b!=t2.b)return t1.b>t2.b;else return t1.c>t2.c;}
  108.     #define tri triple<int,int,int>
  109.     #define trll triple<ll,ll,ll>
  110.  
  111.  
  112.     //for 1 based arrays 
  113.  
  114.     #define FI2(n) for(int i=1;i<=(n);++i)
  115.     #define FJ2(n) for(int j=1;j<=(n);++j)
  116.     #define FK2(n) for(int k=1;k<=(n);++k)
  117.     //for 0 based indexed arrays 
  118.     #define FI(n) for(long i=0;i<(n);i++)
  119.     #define FJ(n) for(long long j=0;j<(n);j++)
  120.     #define FK(n) for(int k=0;k<(n);++k)
  121.     #define FL(n) for(int l=0;l<(n);++l)
  122.     #define FQ(n) for(int q=0;q<(n);++q)
  123.     #define FOR(i,a,b) for(int i = (a), __e = (int) (b); i < __e; ++i)
  124.     #define all(a) std::begin(a), std::end(a)
  125.     #define reunique(v) v.resize(std::unique(v.begin(), v.end()) - v.begin())
  126.  
  127.     #define sqr(x) ((x) * (x))
  128.     #define sqrt(x) sqrt(1.0 * (x))
  129.     #define pow(x, n) pow(1.0 * (x), n)
  130.  
  131.     #define COMPARE(obj) [&](const std::decay_t<decltype(obj)>& a, const std::decay_t<decltype(obj)>& b)
  132.     #define COMPARE_BY(obj, field) [&](const std::decay_t<decltype(obj)>& a, const std::decay_t<decltype(obj)>& b) { return a.field < b.field; }
  133.  
  134.     #define checkbit(n, b) (((n) >> (b)) & 1)
  135.     #define setbit(n, b) ((n) | (static_cast<std::decay_t<decltype(n)>>(1) << (b)))
  136.     #define removebit(n, b) ((n) & ~(static_cast<std::decay_t<decltype(n)>>(1) << (b)))
  137.     #define flipbit(n, b) ((n) ^ (static_cast<std::decay_t<decltype(n)>>(1) << (b)))
  138.     inline int countBits(uint v){v=v-((v>>1)&0x55555555);v=(v&0x33333333)+((v>>2)&0x33333333);return((v+(v>>4)&0xF0F0F0F)*0x1010101)>>24;}
  139.     inline int countBits(ull v){uint t=v>>32;uint p=(v & ((1ULL << 32) - 1)); return countBits(t) + countBits(p); }
  140.     inline int countBits(ll v){return countBits((ull)v); }
  141.     inline int countBits(int v){return countBits((uint)v); }
  142.     unsigned int reverseBits(uint x){ x = (((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1)); x = (((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2)); x = (((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4)); x = (((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8)); return((x >> 16) | (x << 16)); }
  143.     template<class T> inline int sign(T x){ return x > 0 ? 1 : x < 0 ? -1 : 0; }
  144.     inline bool isPowerOfTwo(int x){ return (x != 0 && (x&(x - 1)) == 0); }
  145.     constexpr ll power(ll x, int p) { return p == 0 ? 1 : (x * power(x, p - 1)); }
  146.     template<class T1, class T2, class T3> T1 inline clamp(T1 x, const T2& a, const T3& b) { if (x < a) return a; else if (x > b) return b; else return x; }
  147.     unsigned long long rdtsc() { unsigned long long ret = 0;
  148.     #ifdef __clang__
  149.         return __builtin_readcyclecounter();
  150.     #endif
  151.     #ifndef _MSC_VER
  152.         asm volatile("rdtsc" : "=A" (ret) : :);
  153.     #endif
  154.         return ret; }
  155.     // Fast IO ********************************************************************************************************
  156.     const int __BS = 4096;
  157.     static char __bur[__BS + 16], *__er = __bur + __BS, *__ir = __er;
  158.     template<class T = int> T readInt() {
  159.         auto c = [&]() { if (__ir == __er) std::fill(__bur, __bur + __BS, 0), cin.read(__bur, __BS), __ir = __bur; };
  160.         c(); while (*__ir && (*__ir < '0' || *__ir > '9') && *__ir != '-') ++__ir; c();
  161.         bool m = false; if (*__ir == '-') ++__ir, c(), m = true;
  162.         T r = 0; while (*__ir >= '0' && *__ir <= '9') r = r * 10 + *__ir - '0', ++__ir, c();
  163.         ++__ir; return m ? -r : r;
  164.     }
  165.     static char __buw[__BS + 20], *__iw = __buw, *__ew = __buw + __BS;
  166.     template<class T>
  167.     void writeInt(T x, char endc = '\n') {
  168.         if (x < 0) *__iw++ = '-', x = -x; if (x == 0) *__iw++ = '0';
  169.         char* s = __iw;
  170.         while (x) { T t = x / 10; char c = x - 10 * t + '0'; *__iw++ = c; x = t; }
  171.         char* f = __iw - 1; while (s < f) swap(*s, *f), ++s, --f;
  172.         if (__iw > __ew) cout.write(__buw, __iw - __buw), __iw = __buw;
  173.         *__iw++ = endc;
  174.     }
  175.     template<class T>
  176.     void writeStr(const T& str) {
  177.         int i = 0; while (str[i]) { *__iw++ = str[i++]; if (__iw > __ew) cout.write(__buw, __iw - __buw), __iw = __buw; }
  178.     }
  179.     struct __FL__ { ~__FL__() { if (__iw != __buw) cout.write(__buw, __iw - __buw); } };
  180.     static __FL__ __flushVar__;
  181.  
  182.     //STL output *****************************************************************************************************
  183.     #define TT1 template<class T>
  184.     #define TT1T2 template<class T1, class T2>
  185.     #define TT1T2T3 template<class T1, class T2, class T3>
  186.     TT1T2 ostream& operator << (ostream& os, const pair<T1, T2>& p);
  187.     TT1 ostream& operator << (ostream& os, const vector<T>& v);
  188.     TT1T2 ostream& operator << (ostream& os, const set<T1, T2>&v);
  189.     TT1T2 ostream& operator << (ostream& os, const multiset<T1, T2>&v);
  190.     TT1T2 ostream& operator << (ostream& os, priority_queue<T1, T2> v);
  191.     TT1T2T3 ostream& operator << (ostream& os, const map<T1, T2, T3>& v);
  192.     TT1T2T3 ostream& operator << (ostream& os, const multimap<T1, T2, T3>& v);
  193.     TT1T2T3 ostream& operator << (ostream& os, const triple<T1, T2, T3>& t);
  194.     template<class T, size_t N> ostream& operator << (ostream& os, const array<T, N>& v);
  195.     TT1T2 ostream& operator << (ostream& os, const pair<T1, T2>& p){ return os <<"("<<p.first<<", "<< p.second<<")"; }
  196.     TT1 ostream& operator << (ostream& os, const vector<T>& v){       bool f=1;os<<"[";for(auto& i : v) { if (!f)os << ", ";os<<i;f=0;}return os << "]"; }
  197.     template<class T, size_t N> ostream& operator << (ostream& os, const array<T, N>& v) {     bool f=1;os<<"[";for(auto& i : v) { if (!f)os << ", ";os<<i;f=0;}return os << "]"; }
  198.     TT1T2 ostream& operator << (ostream& os, const set<T1, T2>&v){    bool f=1;os<<"[";for(auto& i : v) { if (!f)os << ", ";os<<i;f=0;}return os << "]"; }
  199.     TT1T2 ostream& operator << (ostream& os, const multiset<T1,T2>&v){bool f=1;os<<"[";for(auto& i : v) { if (!f)os << ", ";os<<i;f=0;}return os << "]"; }
  200.     TT1T2T3 ostream& operator << (ostream& os, const map<T1,T2,T3>& v){ bool f = 1; os << "["; for (auto& ii : v) { if (!f)os << ", "; os << "(" << ii.first << " -> " << ii.second << ") "; f = 0; }return os << "]"; }
  201.     TT1T2 ostream& operator << (ostream& os, const multimap<T1, T2>& v){ bool f = 1; os << "["; for (auto& ii : v) { if (!f)os << ", "; os << "(" << ii.first << " -> " << ii.second << ") "; f = 0; }return os << "]"; }
  202.     TT1T2 ostream& operator << (ostream& os, priority_queue<T1, T2> v) { bool f = 1; os << "["; while (!v.empty()) { auto x = v.top(); v.pop(); if (!f) os << ", "; f = 0; os << x; } return os << "]"; }
  203.     TT1T2T3 ostream& operator << (ostream& os, const triple<T1, T2, T3>& t){ return os << "(" << t.a << ", " << t.b << ", " << t.c << ")"; }
  204.     TT1T2 void printarray(const T1& a, T2 sz, T2 beg = 0){ for (T2 i = beg; i<sz; i++) cout << a[i] << " "; cout << endl; }
  205.  
  206.     //STL input *****************************************************************************************************
  207.     TT1T2T3 inline istream& operator >> (istream& os, triple<T1, T2, T3>& t);
  208.     TT1T2 inline istream& operator >> (istream& os, pair<T1, T2>& p) { return os >> p.first >> p.second; }
  209.     TT1 inline istream& operator >> (istream& os, vector<T>& v) {
  210.         if (v.size()) for (T& t : v) os >> t; else {
  211.             string s; T obj; while (s.empty()) {getline(os, s); if (!os) return os;}
  212.             stringstream ss(s); while (ss >> obj) v.push_back(obj);
  213.         }
  214.         return os;
  215.     }
  216.     TT1T2T3 inline istream& operator >> (istream& os, triple<T1, T2, T3>& t) { return os >> t.a >> t.b >> t.c; }
  217.  
  218.     //Pair magic *****************************************************************************************************
  219.     #define PT1T2 pair<T1, T2>
  220.     TT1T2 inline PT1T2 operator+(const PT1T2 &p1 , const PT1T2 &p2) { return PT1T2(p1.first + p2.first, p1.second + p2.second); }
  221.     TT1T2 inline PT1T2& operator+=(PT1T2 &p1 , const PT1T2 &p2) { p1.first += p2.first, p1.second += p2.second; return p1; }
  222.     TT1T2 inline PT1T2 operator-(const PT1T2 &p1 , const PT1T2 &p2) { return PT1T2(p1.first - p2.first, p1.second - p2.second); }
  223.     TT1T2 inline PT1T2& operator-=(PT1T2 &p1 , const PT1T2 &p2) { p1.first -= p2.first, p1.second -= p2.second; return p1; }
  224.  
  225.     #undef TT1
  226.     #undef TT1T2
  227.     #undef TT1T2T3
  228.  
  229.     #define FREIN(FILE) freopen(FILE, "rt", stdin)
  230.     #define FREOUT(FILE) freopen(FILE, "wt", stdout)
  231.     #ifdef LOCAL
  232.     #define BEGIN_PROFILE(idx, name) int profileIdx = idx; profileName[profileIdx] = name; totalTime[profileIdx] -= rdtsc() / 1e3;
  233.     #define END_PROFILE totalTime[profileIdx] += rdtsc() / 1e3; totalCount[profileIdx]++;
  234.     #else
  235.     #define BEGIN_PROFILE(idx, name)
  236.     #define END_PROFILE
  237.     #endif
  238.  
  239.     template<class T> inline void normmod(T &x, T m) { x %= m; if (x < 0) x += m; }
  240.     template<class T1, class T2> inline T2 summodfast(T1 x, T1 y, T2 m) { T2 res = x + y; if (res >= m) res -= m; return res; }
  241.     template<class T1, class T2, class T3> inline void addmodfast(T1 &x, T2 y, T3 m) { x += y; if (x >= m) x -= m; }
  242.     template<class T1, class T2, class T3> inline void submodfast(T1 &x, T2 y, T3 m) { x -= y; if (x < 0) x += m; }
  243.     #if INTPTR_MAX == INT32_MAX or !defined(__SIZEOF_INT128__)
  244.     inline ll mulmod(ll x, ll n, ll m){ ll r = 0; normmod(x, m); normmod(n, m); while (n) { if (n & 1) r += x; x += x; if (r >= m) r -= m; if (x >= m) x -= m; n /= 2; } return r; }
  245.     #else
  246.     using int128 = __int128;
  247.     inline ll mulmod(ll x, ll n, ll m){ return __int128(x) * n % m; }
  248.     #endif
  249.     inline ll powmod(ll x, ll n, ll m){ ll r = 1; normmod(x, m); while (n){ if (n & 1)r = (r*x) % m; x = (x*x) % m; n /= 2; }return r; }
  250.     inline ll powmulmod(ll x, ll n, ll m) { ll res = 1; normmod(x, m); while (n){ if (n & 1)res = mulmod(res, x, m); x = mulmod(x, x, m); n /= 2; } return res; }
  251.     template<class T> inline T gcd(T a, T b) { while (b) { a %= b; T t = a; a = b; b = t; } return a; }
  252.     inline ll lcm(ll a, ll b){ return a / gcd(a, b) * b; }
  253.     template<class T> inline T gcd(T a, T b, T c){ return gcd(gcd(a, b), c); }
  254.     ll gcdex(ll a, ll b, ll& x, ll& y) {
  255.         if (!a) { x = 0; y = 1; return b; }
  256.         ll y1; ll d = gcdex(b % a, a, y, y1); x = y1 - (b / a) * y;
  257.         return d;
  258.     }
  259.     template<class T> bool isPrime(T x) { if (x <= 4 || x % 2 == 0 || x % 3 == 0) return x == 2 || x == 3;
  260.         for (T i = 5; i * i <= x; i += 6) if (x % i == 0 || x % (i + 2) == 0) return 0; return 1; }
  261.     bool millerRabin(long long n) {
  262.         if (n <= 1000) return isPrime(n);
  263.         long long s = n - 1; int t = 0; while (s % 2 == 0) s /= 2, ++t;
  264.         for (int a : {2, 325, 9375, 28178, 450775, 9780504, 1795265022}) { if (!(a %= n)) return true;
  265.             long long f = powmulmod(a, s, n); if (f == 1 || f == n - 1) continue;
  266.             for (int i = 1; i < t; ++i) if ((f = mulmod(f, f, n)) == n - 1) goto nextp;
  267.             return false; nextp:;
  268.         } return true;
  269.     }
  270.  
  271.  
  272.  
  273.     //some modulus and gcd type functions  
  274.  
  275.  
  276.     const int mod = 1e9 + 7 ;
  277.     ll powmod(ll a,ll b) {ll res=1;if(a>=mod)a%=mod;for(;b;b>>=1){if(b&1)res=res*a;if(res>=mod)res%=mod;a=a*a;if(a>=mod)a%=mod;}return res;}
  278.     ll gcd(ll a , ll b){return a==0?b:gcd(b%a,a);}
  279.     // Useful constants
  280.  
  281.      int some_primes[7] = {24443, 100271, 1000003, 1000333, 5000321, 98765431, 1000000123};
  282.  
  283.  
  284.  
  285.  
  286.     #define T9          1000000000
  287.     #define T18         1000000000000000000LL
  288.     #define INF         1011111111
  289.     #define LLINF       1000111000111000111LL
  290.  
  291.     #define EPS         (double)1e-10
  292.     #define PI          3.14159265358979323846264
  293.     #define link        asaxlajrewqwe
  294.     #define rank        wahayawehasdakw
  295.     // modulo
  296.     #define mod %
  297.     #define NUM  1000000007
  298.     #define NUM1 1000000009
  299.     //scanf type macros 
  300.     #define s(n) scanf("%d", &n)
  301.     #define sl(n) scanf("%ld", &n)
  302.     #define sl3(n1,n2,n3) scanf("%lld %lld %lld ", &n1, &n2, &n3)
  303.     #define sl4(n1,n2,n3,n4) scanf("%ld %ld %ld %ld", &n1, &n2, &n3, &n4)
  304.     #define sll(n) scanf("%I64d", &n)
  305.     #define sll2(n) scanf("%lld", &n)
  306.     //printf type macros 
  307.     #define p(n) printf("%d\n", n)
  308.     #define pl(n) printf("%ld\n",n)
  309.     #define pl3(n1,n2,n3) printf("%lld %lld %lld\n ", n1, n2, n3)
  310.     #define pl4(n1,n2,n3,n4) printf("%ld %ld %ld %ld\n ", n1, n2, n3, n4)
  311.     #define pll(n) printf("%I64d\n",n)
  312.     #define pll2(n) printf("%lld\n",n)
  313.  
  314.  
  315.         //*************************************************************************************
  316.     int32_t solve();
  317.  
  318. // C function for extended Euclidean Algorithm
  319. ll gcdExtended(ll a, ll b, ll *x, ll *y);
  320.  
  321. // Function to find modulo inverse of a
  322. ll modInverse(ll a, ll m)
  323. {
  324.     ll x, y;
  325.     ll g = gcdExtended(a, m, &x, &y);
  326.     if (g != 1){}
  327.         // cout << "Inverse doesn't exist";
  328.     else
  329.     {
  330.         // m is added to handle negative x
  331.         ll res = (x%m + m) % m;
  332.         // cout << "Modular multiplicative inverse is " << 
  333.         return res;
  334.     }
  335. }
  336.  
  337. // C function for extended Euclidean Algorithm
  338. ll gcdExtended(ll a, ll b, ll *x, ll *y)
  339. {
  340.     // Base Case
  341.     if (a == 0)
  342.     {
  343.         *x = 0, *y = 1;
  344.         return b;
  345.     }
  346.  
  347.     ll x1, y1; // To store results of recursive call
  348.     ll gcd = gcdExtended(b%a, a, &x1, &y1);
  349.  
  350.     // Update x and y using results of recursive
  351.     // call
  352.     *x = y1 - (b/a) * x1;
  353.     *y = x1;
  354.  
  355.     return gcd;
  356. }
  357.  
  358.  
  359.     int32_t main(int argc, char** argv) {
  360.  
  361.     ios_base::sync_with_stdio(0);cin.tie(0);
  362.     #ifdef LOCAL
  363.               FREIN("input.txt");
  364.               // FREOUT("out.txt");                                                                                                                                               
  365.     #endif
  366.         return solve();
  367.     }
  368.     //red blue ok but i hate palindromes 
  369.     int32_t solve(){
  370.         int t;l jspecial,n,j,q,qi,Li,Ri,prevli,prevri,i;//qi is the query iterator here 
  371.         ll p,x;
  372.         s(t);
  373.         while(t--){
  374.             x=0;
  375.             sl(n),sll2(p),sl(q);
  376.             ll ppA[n];        //prefix product array 
  377.             ll A[n],prod=1;
  378.             FI(n) {sll2(A[i]);prod=(prod*A[i])%p,ppA[i]=prod;}
  379.  
  380.             //for 2 d matrix storing 
  381.             // for (i = 0; i < n; i++) {
  382.             //     /* code */
  383.             //     prod=A[i]%p;
  384.             //     ppA[i][i]=(prod%p);
  385.             // for (j = i+1; j < n; j++) {
  386.             //     /* code */
  387.             //     prod=(prod%p*A[j]%p)%p;
  388.             //     ppA[i][j]=(prod)%p;
  389.             // }
  390.             // prod=1;
  391.             // }
  392.  
  393.  
  394.  
  395.             // for (i = 0; i < n; i++) {
  396.             //     /* code */
  397.                 for (j = 0; j < n; j++) {
  398.                     /* code */
  399.                     cout<<ppA[j]<<" ";
  400.                 }
  401.                 cout<<"\n";
  402.             // }
  403.  
  404.  
  405.  
  406.  
  407.  
  408.  
  409.             l B[(ll)floor((double)q/(double)64)+2];
  410.             FJ(sizeof(B)/sizeof(B[0])) sl(B[j]);
  411.             // ll sqrtdecompose[(l)ceil(sqrt(n))];
  412.             // builddecompostion(A,p,n,sqrtdecompose);
  413.             // precomputing(A,n,p);
  414.             // l colsize=(l)floor(log(n));
  415.             // ll lookup[n][colsize];
  416.             //sparse table approach preprocessing O(nlogn) query O(1) 
  417.  
  418.             // for (i = 0; i < n; i++) lookup[i][0]=A[i];
  419.             // for (j = 1; (1<<j)<= n; j++)//till logn 
  420.             //     /* code */
  421.             //     for (i = 0; i <= n-(1<<j); i++) {
  422.             //         /* code */
  423.             //         //range 2 ki power hai ya nhi it is an part of an query
  424.             //         lookup[i][j]=((lookup[i][j-1]%p)*((lookup[i+(1<<(j-1))][j-1])%p))%p;
  425.             //     }
  426.             // } //lookup matrix for all possible subarrays of length pow(2,j) for all possible values of j as 0,1,2,3,4,5 up till log(n)
  427.  
  428.  
  429.             //taran rakha                              
  430.  
  431.             for(qi=0;qi<(q);qi++) {
  432.               if(qi%64==0) //here always first it will executes 
  433.              {
  434.                  if(qi==0) x=0;
  435.                  Li = (B[qi/64]  + x)%n, Ri = (B[(qi/64)+1]  + x)%n;
  436.              }
  437.  
  438.               else {Li = (prevli + x)%n, Ri = (prevri + x)%n;}
  439.  
  440.                         if(Li>Ri) swap(Li,Ri);//O(1) time operation 
  441.                     //   x=(lookup[Li][Ri]+1)%p;
  442.                        //(ans(Li,Ri,A,p,n,sqrtdecompose)
  443.                     //     jspecial=(l)log2(Ri-Li+1);      
  444.                     //     if(jspecial%2==0) {x=(lookup[Li][jspecial]+1)%p;}
  445.                     //   else {
  446.                     //       x=(((lookup[Li][jspecial]+lookup[R-(1<<(jspecial))+1][jspecial])/2)+1)%p;
  447.                     //   }
  448.  
  449.                     //   if(ppA[Li]!=0)
  450.                         // x=((((ppA[Ri])/ppA[Li-1]))+1)%p;
  451.                         // std::cout << ppA[Li][Ri-Li] << std::endl;
  452.  
  453.  
  454.         // <---                    @taran check from here --->
  455.  
  456.  
  457.                         x=(((ppA[Ri])*(modInverse(ppA[Li-1],p)))%p+1)%p;
  458.                         //   else  
  459.  
  460.  
  461.  
  462.                         prevli=Li,prevri=Ri;
  463.  
  464.             }
  465.  
  466.  
  467.  
  468.              pll2(x%p);
  469.  
  470.         }
  471.  
  472.         return 0;
  473.     } 
  474.  
  475.  
  476.  
  477.  
  478.     //sq root decompostion tehcnique used 
  479.  
  480.  
  481.  
  482.     // #define MAX 1000000  
  483.     // ll lookup[MAX][MAX]; 
  484.     // void builddecompostion(ll A[],ll p,l n,ll sqrtdecompose[]){
  485.     //     l blocksize=(l)ceil(sqrt(n));
  486.     //     l decomposeitera=0;
  487.     //     ll prod=1;
  488.     //     for (l i = 0; i < n; i++) {
  489.     //             /* code */
  490.     //         prod=((prod*A[i]));
  491.     //         if(i+1%blocksize==0) {
  492.     //                 sqrtdecompose[decomposeitera++]=prod;
  493.     //                 prod=1;
  494.     //         }
  495.  
  496.     //     }    
  497.     // }
  498.  
  499.  
  500.     // ll ans(l Li,l Ri,ll A[],ll p,l n,ll sqrtdecompose[]){
  501.  
  502.     //     l blocksize=(l)ceil(sqrt(n));
  503.     //     // int blockno=Li/blocksize;
  504.     //     ll prod=1;
  505.     //     //case 1 starting case handle alsos true when itis not overlapping any  block  completely 
  506.     //     while(Li%blocksize!=0&&Li<=Ri){
  507.     //         prod=((prod)*A[Li])%p;//add %p here 
  508.     //         Li++;
  509.     //     }
  510.     //     // prod%=p; case 2 for complete overlapping 
  511.     //     while(Li+blocksize<=Ri){
  512.     //         prod=((prod)*((sqrtdecompose[Li/blocksize])))%p;
  513.     //         Li+=blocksize; 
  514.     //     }    
  515.     //     // case3 remainig n unoverlapped elements 
  516.     //     while(Li<=Ri)    {
  517.     //         prod=((prod)*(A[Li]))%p;Li++;//add %p here 
  518.     //     }
  519.  
  520.     //     return prod;
  521.  
  522.     // }
  523.  
  524.  
  525. // 1 approach of the precomputing with theu se of an GLOBAL LOOKUP MATRIX OF SIZE MAX MAX...            
  526. // void precomputing(ll A[],l n,ll p){
  527. //     l i;
  528. //     for (l j= 0; j < (l)log(n); ++j)
  529. //     {
  530. //         i=0;
  531. //         /* code */
  532. //         while(i<n)
  533. //         {
  534. //             /* code */
  535. //             if(j==0) lookup[i][j]=i;
  536. //             else {
  537. //                 lookup[i][j]=((lookup[i][j-1]%p)*(lookup[i + (1<<(j-1))][j-1])%p)%p;
  538. //             }
  539. //             i++; 
  540. //         }
  541. //     }
  542.  
  543. // }
Success #stdin #stdout 0s 4520KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/PIxj0c
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

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!