fork download
copy 
  1. // ROOT : DRAGON3012009 : WA in Real Life
  2. #include <bits/stdc++.h>
  3. #define FOR(i,l,r) for(int i = l ; i <= r ; i ++)
  4. #define FORD(i,r,l) for(int i = r ; i >= l ; i --)
  5. #define REP(i, a ) for(int i = 0 ; i < a ; i ++ )
  6. #define compare(v) sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end());
  7. #define ll long long
  8. #define el "\n"
  9. #define fi first
  10. #define se second
  11. #define _ROOT_ int main()
  12. #define M 1000000007
  13. #define MAXN 300003
  14. #define INF (1ll<<60 )
  15. #define NAME "post"
  16. #define LOG 63
  17. #define BLOCK 475
  18. #define debug(a) cout << #a << " = " << a << endl;
  19. using namespace std;
  20.  
  21. ll n, m, q ;
  22. ll a[MAXN] ;
  23. ll pref[MAXN ] ;
  24. ll b[MAXN] ;
  25. ll res[MAXN ] ;
  26. ll cnt[MAXN ] ;
  27. ll ans ;
  28. vector<ll> cpr ;
  29. unordered_map<ll,ll> mp ;
  30. vector<ll> pos[MAXN ] ;
  31.  
  32. struct Query {
  33.     ll l, r, id ;
  34.     bool operator < (const Query & other ) const {
  35.         ll A = l / BLOCK, B = other.l / BLOCK ;
  36.         if(A == B ) return (A % 2 == 1 ? r > other.r : r < other.r ) ;
  37.         return A < B ;
  38.     }
  39. } ;
  40.  
  41. vector<Query> que ;
  42. ll rands(ll l, ll r ) {
  43.     return rand() % (r - l + 1 ) + l ;
  44. }
  45. ll random_50 () {
  46.     ll res = 0 ;
  47.     FOR(i, 0, LOG ) if(rands(0, 1 )) res += (1LL << i) ;
  48.     if(mp[res]) return random_50() ;
  49.     else {
  50.         mp[res] = true ;
  51.         return res ;
  52.     }
  53. }
  54.  
  55. void add(ll a ) {
  56.     ans += cnt[a] ;
  57.     cnt[a] ++ ;
  58. }
  59.  
  60. void del(ll a ) {
  61.     cnt[a] -- ;
  62.     ans -= cnt[a] ;
  63. }
  64.  
  65. ll ID(ll value ) {
  66.     return lower_bound(cpr.begin(), cpr.end(), value  ) - cpr.begin() + 1 ;
  67. }
  68.  
  69. void init() {
  70.     cin >> n >> q ;
  71.     FOR(i, 1, n ) {
  72.         cin >> a[i] ;
  73.         cpr.push_back(a[i]);
  74.     }
  75.     FOR(i, 1, q ) {
  76.         ll l, r ;
  77.         cin >> l >> r ;
  78.         que.push_back({l, r, i }) ;
  79.     }
  80. }
  81.  
  82. void solve() {
  83.  
  84.     compare(cpr ) ;
  85.     FOR(i, 1, n ) a[i] = ID(a[i] ) ;
  86.     FOR(i, 1, n ) b[i] = random_50() ;
  87. //    FOR(i , 1 , n ) cout << b[i] << " " ; cout << " ran " << el ;
  88.     FOR(i, 1, n ) pos[a[i]].push_back(b[i]) ;
  89.  
  90.     FOR(i, 1,(int) cpr.size() ) {
  91.         ll p = rands(1, pos[i].size() ) ;
  92.         p -- ;
  93.         ll cur = 0 ;
  94.         for(ll j = 0 ; j < pos[i].size() ; j ++ ) if(j != p ) cur ^= pos[i][j] ;
  95.         pos[i][p] = cur ;
  96.     }
  97.  
  98.     FOR(i, 1,(int) cpr.size() ) random_shuffle(pos[i].begin(), pos[i].end() ) ;
  99.  
  100.     FOR(i, 1, n ) {
  101.         ll t = a[i] ;
  102.         a[i] = pos[t].back() ;
  103.         pos[t].pop_back() ;
  104.     }
  105.     cpr.clear() ;
  106.  
  107.     FOR(i, 1, n ) {
  108.         pref[i] = pref[i - 1 ] ^ a[i] ;
  109.     }
  110.  
  111. //        FOR(i , 0 , n ) cout << pref[i] << " " ; cout << " pref " << el ;
  112.  
  113.  
  114. //    FOR(i , 1 , n ) cout << a[i] << " " ;
  115.     FOR(i, 0, n ) cpr.push_back(pref[i]) ;
  116.     compare(cpr ) ;
  117.     FOR(i, 0, n ) pref[i] = ID(pref[i]) ;
  118.  
  119. //    cnt[ID(0) ] ++ ;
  120.     sort(que.begin(), que.end() ) ;
  121. //    FOR(i , 0 , n ) cout << pref[i] << " " ; cout << " pref " << el ;
  122.     ll l = 0, r = -1 ;
  123.  
  124.     for(auto [l1, r1, id ] : que ) {
  125.         l1 -- ;
  126.         while(r < r1 ) add(pref[++ r ]) ;
  127.         while(l > l1 ) add(pref[-- l ]) ;
  128.         while(l < l1 ) del(pref[l ++ ]) ;
  129.         while(r > r1 ) del(pref[r -- ]) ;
  130.         res[id] = ans ;
  131.     }
  132.  
  133.     FOR(i, 1, q ) cout << res[i] << el ;
  134. }
  135.  
  136. _ROOT_ {
  137.      freopen(NAME".inp" , "r" , stdin);
  138.      freopen(NAME".out" , "w", stdout) ;
  139.     ios_base::sync_with_stdio(0);
  140.     cin.tie(0);
  141.     cout.tie(0);
  142.     srand(time(nullptr)) ;
  143.     int t = 1; // cin >> t ;
  144.     while(t--) {
  145.         init();
  146.         solve();
  147.     }
  148.     return (0&0);
  149. }
  150.  
Success #stdin #stdout 0.01s 12448KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/QB8YEH
language:
C++14 (gcc 8.3)
created:
1 day 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!