Advertisement
Guest User

Untitled

a guest
Sep 22nd, 2019
89
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.48 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define _ ios_base::sync_with_stdio(0);cin.tie(0);
  6. #define endl '\n'
  7. #define sc(a) scanf("%d",&a)
  8. #define sc2(a,b) sc(a), sc(b)
  9. #define pri(x) printf("%d\n",x)
  10. #define f first
  11. #define s second
  12. #define pb push_back
  13.  
  14. typedef long long ll;
  15. typedef pair<int, int> ii;
  16.  
  17. const int INF = 0x3f3f3f3f;
  18. const ll LINF = 0x3f3f3f3f3f3f3f3fll;
  19.  
  20. const int D = 2;
  21. const int MAX = 100;
  22. int n;
  23.  
  24. vector<ll> bit[1<<D];
  25.  
  26. void build() {
  27.     int sz = 1;
  28.     for (int i = 0; i < D; i++) sz *= MAX;
  29.     for (int i = 0; i < (1<<D); i++)
  30.         bit[i] = vector<ll>(sz+10, 0);
  31. }
  32.  
  33. void updatep(int i, vector<int>& p, ll k, int it=0) {
  34.     if (it == D) {
  35.         int pos = 0, power = 1;
  36.         for (int i = 0; i < p.size(); i++) {
  37.             pos += p[i]*power;
  38.             power *= n;
  39.         }
  40.         bit[i][pos] += k;
  41.         return;
  42.     }
  43.     for (int x = p[it]; x <= n; x += x&-x) {
  44.         int tmp = p[it]; p[it] = x;
  45.         updatep(i, p, k, it+1);
  46.         p[it] = tmp;
  47.     }
  48. }
  49.  
  50. void updater(int i, vector<int>& p1, vector<int> & p2, ll k) {
  51.     for (int i = 0; i < (1<<D); i++) {
  52.         vector<int> P;
  53.         for (int j = 0; j < D; j++)
  54.             P.push_back((i&(1<<j)) ? p1[j] : p2[j]+1);
  55.         updatep(i, P, (__builtin_popcount(i)%2) ? -k : k);
  56.     }
  57. }
  58.  
  59. ll queryp(int i, vector<int>& p, int it=0) {
  60.     if (it == D) {
  61.         int pos = 0, power = 1;
  62.         for (int i = 0; i < p.size(); i++) {
  63.             pos += p[i]*power;
  64.             power *= n;
  65.         }
  66.         return bit[i][pos];
  67.     }
  68.     ll ans = 0;
  69.     for (int x = p[it]; x; x -= x&-x) {
  70.         int tmp = p[it]; p[it] = x;
  71.         ans += queryp(i, p, k, it+1);
  72.         p[it] = tmp;
  73.     }
  74.     return ans;
  75. }
  76.  
  77. void update(vector<int>& p1, vector<int>& p2, ll k) {
  78.     for (int i = 0; i < (1<<D); i++) {
  79.         for (int j = 0; j < (1<<__builtin_popcount(i)); j++) {
  80.             vector<pt> P1, P2; ll K = k;
  81.             for (int jj = 0; jj < D; jj++) {
  82.                 P1.push_back((j&(1<<jj)) ? p2[j]+1 : p1[j]);
  83.                 P2.push_back((j&(1<<jj)) ? n : p2[j])
  84.                 K *= ((j&(1<<jj)) ? p2[j]-p1[j]+1 : p1[j]-1)
  85.             }
  86.             updater(i, P1, P2, (__builtin_popcount(j)%2) ? -k : k);
  87.         }  
  88.     }
  89. }
  90.  
  91. ll queryP(vector<int>& p) {
  92.     ll ans = 0;
  93.     for (int i = 0; i < (1<<D); i++) {
  94.         ll x = queryp(i, p1);
  95.         for (int j = 0; j < D; j++) if (!(i&(1<<j))) x *= p[j];
  96.         ans += x;
  97.     }
  98.     return ans;
  99. }
  100.  
  101. ll query(vector<int>& p1, vector<int>& p2) {
  102.     ll ans = 0;
  103.     for (int i = 0; i < (1<<D); i++) {
  104.         vector<int> P;
  105.         for (int j = 0; j < D; j++)
  106.             P.push_back((i&(1<<j)) ? p1[j]-1 : p2[j]);
  107.         ll add = queryP(P);
  108.         ans += (__builtin_popcount(i)%2) ? -add : add;
  109.     }
  110.     return ans;
  111. }
  112.  
  113. int main() {
  114.     exit(0);
  115. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement