N 個の要素と N 個の範囲を持つ配列 A が与えられます。それぞれ [L, R] の形式です。範囲の値を、インデックス L からインデックス R までの A のすべての要素の合計と呼びます。
例 : 配列 A = [2 5 7 9 8] とし、範囲を [2,4] とすると、この範囲の値は 5+7+9=21 になります。
ここで、2 つのタイプのいずれかのクエリごとに Q 個のクエリが与えられます。
1. 0 X Y : It means change Xth element of array to Y.
2. 1 A B : It means we need to report the sum of values of ranges from A to B.
例:配列 A = [2 3 7 8 6 5] とし、3 つの範囲があるとします。
R1: [1,3] Then value corresponding to this range is 2+3+7=12
R2: [4,5] Then value corresponding to this range is 8+6=14
R3: [3,6] Then value corresponding to this range is 7+8+6+5=26
次に、3 つのクエリを作成します。
Q1: 1 1 2
Then here answer is value of Range1 + value of Range2 = 12+14=26
Q2: 0 2 5
It means Change 2nd element to 5 from 3.It will change the result of Range 1.
Now value of Range1 becomes 2+5+7=14
Q3: 1 1 2
Then here answer is value of Range1 + value of Range2 = 14+14=28
10^5 のクエリがあり、N も 10^5 までの場合の方法。効率的な方法で Queries2 に報告するにはどうすればよいですか?
私のアプローチ：最初のクエリは簡単に処理できます。配列からセグメント ツリーを構築できます。これを使用して、最初の配列 (2 番目の配列の要素) の間隔の合計を計算できます。しかし、O(log n) で 2 番目のクエリを処理するにはどうすればよいですか? 最悪の場合、更新する要素は 2 番目の配列のすべての間隔に含まれます。
O(Qlog N) または O(Q(logN)^2) ソリューションが必要です。
明らかに、各クエリに O(N) を使用することはできません。効率的な方法を取得するのを手伝ってください
私の現在のコード：
#include<bits/stdc++.h>
using namespace std;
long long arr[100002],i,n,Li[100002],Ri[100002],q,j;
long long queries[100002][2],query_val[100002],F[100002],temp;
long long ans[100002];
int main()
{
scanf("%lld",&n);
for(i=1;i<=n;i++)
scanf("%lld",&arr[i]);
for(i=1;i<=n;i++)
{
scanf("%lld%lld",&Li[i],&Ri[i]);
}
for(i=1;i<=n;i++)
{
F[n] = 0;
ans[i] = 0;
}
scanf("%lld",&q);
for(i=1;i<=q;i++)
{
scanf("%lld",&query_val[i]);
scanf("%lld%lld",&queries[i][0],&queries[i][1]);
}
for(i=1;i<=n;i++)
{
for(j=Li[i];j<=Ri[i];j++)
{
F[i] = F[i] + arr[j];
}
}
long long diff;
long long ans_count = 0,k=1;
for(i=1;i<=q;i++)
{
if(query_val[i] == 1)
{
temp = arr[queries[i][0]];
arr[queries[i][0]] = queries[i][1];
diff = arr[queries[i][0]] - temp;
for(j=1;j<=n;j++)
{
if(queries[i][0]>=Li[j] && queries[i][0]<=Ri[j])
F[j] = F[j] + diff;
++k;
}
}
else if(query_val[i] == 2)
{
++ans_count;
for(j=queries[i][0];j<=queries[i][1];j++)
ans[ans_count] = ans[ans_count] + F[j];
}
}
for(i=1;i<=ans_count;i++)
{
printf("%lld\n",ans[i]);
}
return 0;
}
コードは正しいですが、大規模なテスト ケースの場合は膨大な時間がかかります。助けてください