MinhNGUYEN2k4

Untitled

Sep 18th, 2021
652
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //Nguyen Huu Hoang Minh
  2. #include <bits/stdc++.h>
  3. #define sz(x) int(x.size())
  4. #define all(x) x.begin(),x.end()
  5. #define reset(x) memset(x, 0,sizeof(x))
  6. #define pb push_back
  7. #define mp make_pair
  8. #define fi first
  9. #define se second
  10. #define N 200005
  11. #define remain(x) if (x > MOD) x -= MOD
  12. #define ii pair<int, int>
  13. #define iiii pair< ii , ii >
  14. #define viiii vector< iiii >
  15. #define vi vector<int>
  16. #define vii vector< ii >
  17. #define bit(x, i) (((x) >> (i)) & 1)
  18. #define Task "test"
  19. #define int long long
  20.  
  21. using namespace std;
  22.  
  23. typedef long double ld;
  24. const int inf = 1e10;
  25. const int minf = -1e10;
  26.  
  27. int n, m;
  28.  
  29. struct dat{
  30.     int a, b;
  31. };
  32.  
  33. dat a[N];
  34.  
  35. int bsize;
  36. int nb;
  37. int res[N];
  38.  
  39. struct query{
  40.     int l, r;
  41.     int idx;
  42.     bool operator < (const query& x){
  43.         if ((l-1)/bsize != (x.l-1)/bsize) return (l-1)/bsize < (x.l-1)/bsize;
  44.         return r < x.r;
  45.     }
  46.  
  47. };
  48.  
  49. query Q[N];
  50.  
  51. void readfile()
  52. {
  53.     ios_base::sync_with_stdio(false);
  54.     cin.tie(0);cout.tie(0);
  55.     if (fopen(Task".inp","r"))
  56.     {
  57.         freopen(Task".inp","r",stdin);
  58.         //freopen(Task".out","w",stdout);
  59.     }
  60.     cin >> n >> m;
  61.     for(int i=1; i<=n; i++) cin >> a[i].a;
  62.     bsize = sqrt(n)+1;
  63.     nb = (n-1)/bsize+1;
  64.     for(int i=1; i<=m; i++){
  65.         cin >> Q[i].l >> Q[i].r;
  66.         Q[i].idx = i;
  67.     }
  68.     sort(Q+1,Q+1+m);
  69. }
  70.  
  71. void compress(){
  72.     vector<int> b;
  73.     for(int i=1; i<=n; i++) b.pb(a[i].a);
  74.     sort(b.begin(),b.end());
  75.     b.erase(unique(b.begin(),b.end()),b.end());
  76.     for(int i=1; i<=n; i++){
  77.         int k = lower_bound(all(b),a[i].a)-b.begin();
  78.         a[i].b = b[k];
  79.     }
  80. }
  81.  
  82. int nho[N];
  83. int ans=0;
  84.  
  85. void add(int pos){
  86.     int k = nho[a[pos].b];
  87.     ans = ans - k*k*a[pos].a + (k+1)*(k+1)*a[pos].a;
  88.     nho[a[pos].b]++;
  89. }
  90.  
  91. void del(int pos){
  92.     int k = nho[a[pos].b];
  93.     ans = ans - k*k*a[pos].a + (k-1)*(k-1)*a[pos].a;
  94.     nho[a[pos].b]--;
  95. }
  96.  
  97. void proc()
  98. {
  99.     compress();
  100.     int l = 0, r = 0;
  101.     for(int i=1; i<=m; i++){
  102.         query q = Q[i];
  103.         int u = q.l;
  104.         int v = q.r;
  105.         while (u < l) add(--l);
  106.         while (l < u) del(l++);
  107.         while (r < v) add(++r);
  108.         while (r > v) del(r--);
  109.         res[q.idx] = ans;
  110.     }
  111.     for(int i=1; i<=m; i++) cout << res[i] << '\n';
  112. }
  113.  
  114. signed main()
  115. {
  116.     readfile();
  117.     proc();
  118.     return 0;
  119. }
  120.  
RAW Paste Data