fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define FastRead ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  4. #define int long long int
  5. #define ll int
  6. #define bits_count __builtin_popcountll
  7. #define endl '\n'
  8. #define double long double
  9. #define ld double
  10. #define FOR(i,a,n) for (ll i=(a);i<=(n);++i)
  11. #define RFOR(i,a,n) for (ll i=(n);i>=(a);--i)
  12. #define ZERO(a) memset((a),0,sizeof((a)))
  13. #define MINUS(a) memset((a),-1,sizeof((a)))
  14. #define f first
  15. #define s second
  16. #define pb push_back
  17. #define mk make_pair
  18. #define all(g) g.begin(),g.end()
  19. #define sz(x) (ll)x.size()
  20. #define pr pair<int,int>
  21. int fastMax(int x, int y) { return (((y-x)>>(32-1))&(x^y))^y; }
  22. int fastMin(int x, int y) { return (((y-x)>>(32-1))&(x^y))^x; }
  23.  
  24. // #include <ext/pb_ds/assoc_container.hpp> // Common file
  25. // #include <ext/pb_ds/tree_policy.hpp>     // Including tree_order_statistics_node_updat
  26. // using namespace __gnu_pbds;
  27. // typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
  28. // const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
  29. // struct chash { int operator()(int x) const { return x ^ RANDOM; }};
  30. // cc_hash_table<int, int, hash<int>> cnt;
  31.  
  32. const int MAXN = 1e5 + 10;
  33. const int MOD = 1e9 + 7;
  34. int siz = sqrt(MAXN);
  35. vector<int> que[MAXN];
  36. vector<pair<int,pair<int,int>>> qs;
  37.  
  38. int a[MAXN];
  39. int sum[MAXN];
  40. int pre[MAXN];
  41. int sq[MAXN],cubes[MAXN];
  42. int n,q;
  43.  
  44. void update(){
  45.     int x3 = 0,x2 = 0,x1 = 0,x0 = 0;
  46.  
  47.     FOR(i,1,n){
  48.         for(int x:que[i]){
  49.             if(x >= 0){
  50.                 x3 = (x3 + 1)%MOD; x2 = (x2-3*x)%MOD; x1 = (x1 + (3*x*x)%MOD)%MOD; x0 = (x0 - cubes[x])%MOD; 
  51.                 x2 = (x2 + 6)%MOD; x1 = (x1 - 12*x)%MOD; x0 = (x0 + (6*sq[x])%MOD)%MOD;
  52.                 x1 = (x1 + 11)%MOD; x0 = (x0 - (11*x)%MOD)%MOD;
  53.                 x0 = (x0 + 6)%MOD;
  54.             }else {
  55.                 x = -x;
  56.                 x3 = (x3 - 1)%MOD; x2 = (x2+3*x)%MOD; x1 = (x1 - (3*x*x)%MOD)%MOD; x0 = (x0 + cubes[x])%MOD; 
  57.                 x2 = (x2 - 6)%MOD; x1 = (x1 + 12*x)%MOD; x0 = (x0 - (6*sq[x])%MOD)%MOD;
  58.                 x1 = (x1 - 11)%MOD; x0 = (x0 + (11*x)%MOD)%MOD;
  59.                 x0 = (x0 - 6)%MOD;
  60.             }
  61.         } 
  62.         int val = ((cubes[i-1] * x3)%MOD + ((sq[i-1] * x2)%MOD + ((i-1)*x1)%MOD + x0)%MOD)%MOD;  
  63.         a[i] = (a[i] + val)%MOD;
  64.         pre[i] = (pre[i-1] + a[i])%MOD;
  65.         que[i].clear();
  66.     }
  67.  
  68.     qs.clear();
  69. }
  70.  
  71.  
  72. void solve(){
  73.     cin>>n>>q; 
  74.     FOR(i,1,n) sum[i] = (((i*(i+1))%MOD)*(i+2))%MOD;
  75.     FOR(i,1,n) sum[i] = ((sum[i]+sum[i-1])%MOD + MOD)%MOD;
  76.     FOR(i,1,n) sq[i] = (i*i)%MOD,cubes[i] = (i*i*i)%MOD;
  77.  
  78.     FOR(i,1,q){
  79.         int type; cin>>type;
  80.         int x,y; cin>>x>>y;
  81.  
  82.         if(type == 0){
  83.             int ans = (pre[y] - pre[x-1])%MOD;
  84.             ans = (ans+MOD)%MOD;
  85.             for(auto qx:qs){
  86.                 int xx = qx.s.f,yy = qx.s.s;
  87.                 if(x > yy) continue;
  88.                 else if(xx > y) continue;
  89.                 else {
  90.                     int ox = max(xx,x);
  91.                     int oy = min(yy,y);
  92.                     if(qx.f == 1) ans = (ans + (sum[oy-xx+1] - sum[ox-xx])%MOD)%MOD;
  93.                     else ans = (ans - (sum[oy-xx+1] - sum[ox-xx])%MOD)%MOD; 
  94.                 }
  95.                 if(ans < 0) ans += MOD;
  96.             }    
  97.             cout<<ans<<endl;
  98.         }else if(type == 1){
  99.             que[x].push_back(x-1);
  100.             que[y+1].push_back(-x+1);
  101.             qs.push_back(mk(1,mk(x,y)));
  102.             if(sz(qs) >= siz) update();
  103.         }else {
  104.             que[x].push_back(-x+1);
  105.             que[y+1].push_back(x-1);
  106.             qs.push_back(mk(-1,mk(x,y)));
  107.             if(sz(qs) >= siz) update();
  108.         }
  109.     }
  110. }
  111.  
  112. signed main(){
  113.  
  114.     FastRead;     
  115. #ifndef ONLINE_JUDGE
  116.     freopen("input.txt", "r", stdin);
  117.     freopen("output.txt", "w", stdout);
  118. #endif
  119.  
  120.  
  121.     int t = 1; 
  122.     // cin>>t;
  123.     FOR(i,1,t){
  124.         // cout<<"Case #"<<i<<": ";
  125.         solve();
  126.     }
  127. }
  128.  
Success #stdin #stdout 0s 6132KB
comments (?)
stdin
copy 
8 4
1 1 8
0 2 8
2 4 6
0 5 6
stdout
copy 
1974
462
https://ideone.com/1ldJlg
language:
C++14 (gcc 8.3)
created:
4 years 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!