提出 #32060317

---

ソースコード 拡げる

#include<bits/stdc++.h>
#include<atcoder/all>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define PI acos(-1)
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define mpa make_pair
#define mpt make_tuple
#define emb emplace_back
#define endll "\n"
using namespace std;
using namespace atcoder;
using ll = long long;
constexpr int MAX_BACKET = 448;
constexpr int MAX_N = 200000;
constexpr int MAX_M = 200000;
constexpr int MAX_Q = 200000;
ll imos[MAX_BACKET][MAX_M+1];
int C[MAX_Q],L[MAX_Q],R[MAX_Q],I[MAX_Q],J[MAX_Q],X[MAX_Q];
int Last[MAX_N];
int main(){
  cin.tie(0);ios::sync_with_stdio(false);
  //-----------------------------------------------
  ll N,M,Q;cin >> N >> M >> Q;
  ll sqr = sqrt(Q),backet = (Q+sqr-1)/sqr;
  for(int i=0;i<Q;i++){
    cin >> C[i];
    if(C[i] == 1){
      cin >> L[i] >> R[i] >> X[i];L[i]--;R[i]--;
      imos[i/sqr][L[i]] += X[i];imos[i/sqr][R[i]+1] -= X[i];
    }
    else if(C[i] == 2){
      cin >> I[i] >> X[i];I[i]--;
    }
    else{
      cin >> I[i] >> J[i];I[i]--;J[i]--;
    }
  }
  for(int i=0;i<backet;i++){
    for(int j=1;j<=M;j++) imos[i][j] += imos[i][j-1];
  }
  fill(Last,Last+N,-1);
  for(int i=0;i<Q;i++){
    if(C[i] == 2) Last[I[i]] = i;
    else if(C[i] == 3){
      ll ans = 0;
      if(Last[I[i]] != -1) ans = X[Last[I[i]]];
      int itr = Last[I[i]]+1;
      while(itr < i && itr%sqr){
        if(C[itr] == 1 && L[itr] <= J[i] && J[i] <= R[itr]) ans += X[itr];
        itr++;
      }
      while(itr/sqr < i/sqr){
        ans += imos[itr/sqr][J[i]];itr += sqr;
      }
      while(itr < i){
        if(C[itr] == 1 && L[itr] <= J[i] && J[i] <= R[itr]) ans += X[itr];
        itr++;
      }
      cout << ans << endll;
    }
  }
}

提出情報

ジャッジ結果