D - All Assign Point Add Editorial by kusano
C++のmapを使った解法C++の map<int, int> M
は、 i
が M
に含まれないとき、 M[i]==0
となります。これを利用すると簡潔に解くことができます。
https://atcoder.jp/contests/abc278/editorial/5231 と同様に、 base
からの差分で列を管理することにします。 i
番目の差分を M[i]
とします。 2のクエリで i
が現れていないときは差分が0なので、 M[i]==0
となることは都合が良いです。
base = 0
、M[i] = A[i]
と初期化します- 1のクエリでは、
base = x
とし、M
を初期化します - 2のクエリでは、
M[i] += x
とします - 3のクエリでは、
base + M[i]
を出力します
M.clear()
の計算量はそのときの要素数を \(n\) として \(O(n)\) であり、M
に値が追加されうる2のクエリの個数は \(N\) 未満なので、全ての M.clear()
の計算量を合計しても \(O(N)\) です。
#include <iostream>
#include <vector>
#include <map>
using namespace std;
int main()
{
int N;
cin>>N;
vector<int> A(N);
for (int &a: A)
cin>>a;
int base = 0;
map<int, long long> M;
for (int i=0; i<N; i++)
M[i] = A[i];
int Q;
cin>>Q;
for (int q=0; q<Q; q++)
{
int t;
cin>>t;
if (t==1)
{
int x;
cin>>x;
base = x;
M.clear();
}
if (t==2)
{
int i, x;
cin>>i>>x;
M[i-1] += x;
}
if (t==3)
{
int i;
cin>>i;
cout<<base+M[i-1]<<endl;
}
}
}
posted:
last update: