fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. typedef long double ld;
  5. typedef vector<int> vi;
  6. typedef vector<ld> vld;
  7. typedef vector<ll> vll;
  8. typedef vector<pair<ll, ll>> vp;
  9. typedef pair<int, int> pii;
  10. typedef pair<ll, ll> pll;
  11. #define fr first
  12. #define sc second
  13. #define all(a) a.begin(),a.end()
  14.  
  15.  
  16. void Hendi() {
  17.     ios_base::sync_with_stdio(0);
  18.     cin.tie(0);
  19.     cout.tie(0);
  20. #ifndef ONLINE_JUDGE
  21.     freopen("input.txt", "r", stdin);
  22.     freopen("output.txt", "w", stdout);
  23.     freopen("error.txt", "w", stderr);
  24. #endif
  25. }
  26.  
  27. const ll INF = 1e18;
  28. const ll MOD = 1e9 + 7;
  29. const double EPS = 1e-7;
  30. const int N = 2e5 + 5;
  31. const int N1 = 1e5 + 5;
  32. int dx[] = {0, 0, 1, -1, -1, -1, 1, 1};
  33. int dy[] = {1, -1, 0, 0, 1, -1, 1, -1};
  34. char di[] = {'R', 'L', 'D', 'U'};
  35.  
  36. ll mul(ll a, ll b) {
  37.     return ((a % MOD) * (b % MOD)) % MOD;
  38. }
  39.  
  40. ll sub(ll a, ll b) {
  41.     return ((a % MOD) - (b % MOD) + MOD) % MOD;
  42. }
  43.  
  44. ll MOD_add(ll a, ll b) {
  45.     return ((a % MOD) + (b % MOD)) % MOD;
  46. }
  47.  
  48. int SQ = 450;
  49. struct BIT{
  50.     int n;
  51.     vll tree;
  52.  
  53.     BIT(int n){
  54.         tree.resize(n + 1,0);
  55.         this-> n = n;
  56.     }
  57.     ll get(int i){
  58.         ++i;
  59.         ll sum = 0;
  60.         while(i >= 1){
  61.             sum += tree[i];
  62.             i -= (i & -i);
  63.         }
  64.         return sum;
  65.     }
  66.     void add(int i , ll val){
  67.         ++i;
  68.         while(i <= n){
  69.             tree[i] += val;
  70.             i += (i & -i);
  71.         }
  72.     }
  73.     ll query(int l , int r){
  74.         return get(r) - get(l - 1);
  75.     };
  76. };
  77.  
  78. struct query {
  79.     int l, r ,idx;
  80.     bool operator <(query &other) {
  81.         if (l / SQ != other.l / SQ) return l / SQ < other.l / SQ;
  82.         return ((l / SQ) & 1? r < other.r: r > other.r);
  83.     }
  84. };
  85.  
  86. ll pw(ll a , ll b){
  87.     if(b == 0) return 1;
  88.     ll ans = pw(a, b / 2);
  89.     ans = mul(ans, ans);
  90.     if(b & 1) ans = mul(ans, a);
  91.     return ans;
  92. }
  93.  
  94. void solve() {
  95.     int n , q;
  96.     cin>> n;
  97.     vll a(n);
  98.     for (int i = 0; i < n; ++i) {
  99.         cin>> a[i];
  100.     }
  101.     cin>> q;
  102.     vector<query> v(q);
  103.     for (int i = 0; i < q; ++i) {
  104.         cin>> v[i].l >> v[i].r;
  105.         v[i].l--;
  106.         v[i].r--;
  107.         v[i].idx = i;
  108.     }
  109.     sort(all(v));
  110.     BIT bit(n + 1);
  111.     ll sum = 0;
  112.     int l = 0, r = - 1;
  113.     vll ans(q);
  114.     auto add = [&](int idx, int dir) {
  115.         if(dir == 0) sum = MOD_add(sum, bit.get(a[idx] - 1));
  116.         else sum = MOD_add(sum, bit.query(a[idx] + 1 , n));
  117.         bit.add(a[idx], 1);
  118.     };
  119.  
  120.     auto del = [&](int idx, int dir) {
  121.         if(dir == 0) sum = sub(sum, bit.get(a[idx] -1 ));
  122.         else sum = sub(sum, bit.query(a[idx] + 1 , n));
  123.         bit.add(a[idx], -1);
  124.     };
  125.  
  126.     auto query = [&]() {
  127.         return mul(sum, pw(2, r - l - 1));
  128.     };
  129.     for (auto & [lq,rq,idx]: v) {
  130.         while (l > lq) add(--l, 0);
  131.         while (r < rq) add(++r, 1);
  132.         while (l < lq) del(l++, 0);
  133.         while (r > rq) del(r--, 1);
  134.         ans[idx] = query();
  135.     }
  136.     for (auto &i : ans) {
  137.         cout<< i << '\n';
  138.     }
  139. }
  140.  
  141.  
  142. int main() {
  143.     Hendi();
  144.     int T = 1;
  145.      cin >> T;
  146.     while (T--) {
  147.         solve();
  148.     }
  149. }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/2JWYD2
language:
C++ (gcc 8.3)
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!