#include <bits/stdc++.h>
using namespace std;
vector <long long int> update(int x,long long int val,vector <long long int> b,int n)
{
b[x]+=(val);
x+=(x&-x);
while(x<=n)
{
b[x]+=(val);
x+=(x&-x);
}
return b;
}
long long int getsum(int i,int j,vector <long long int> b)
{
i=i-1;
long long int sum1=b[i];
i-=(i&-i);
while(i>0)
{
sum1+=(b[i]);
i-=(i&-i);
}
long long int sum2=b[j];
j-=(j&-j);
while(j>0)
{
sum2+=b[j];
j-=(j&-j);
}
return(sum2-sum1);
}
int main()
{
int n,q;
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n>>q;
vector <int> h(n);
for(int i=0;i<n;i++)
{
cin>>h[i];
}
vector <long long int> a(n);
for(int i=0;i<n;i++)
{
cin>>a[i];
}
vector <int> Pl(n,-1);
vector <int> Pr(n,-1);
stack <int> s;
s.push(0);
for(int i = 1; i < n; i++)
{
if (s.empty())
{
s.push(i);
continue;
}
while (s.empty() == false && h[s.top()] < h[i])
{
Pl[s.top()] = i;
s.pop();
}
s.push(i);
}
while(s.empty()==false)
{
s.pop();
}
s.push(n-1);
// iterate for rest of the elements
for(int i = n-2; i >= 0; i--)
{
if (s.empty())
{
s.push(i);
continue;
}
while (s.empty() == false && h[s.top()] < h[i])
{
Pr[s.top()] = i;
s.pop();
}
s.push(i);
}
while(s.empty()==false)
{
s.pop();
}
vector <pair <int,int>> timel(n);
vector <int> arrayl;
s.push(0);
int t = 1;
timel[0].first = t;
t++;
arrayl.push_back(0);
arrayl.push_back(a[0]);
int i = 1;
while(i<n)
{
if(s.empty())
{
s.push(i);
timel[i].first = t;
t++;
arrayl.push_back(a[i]);
i++;
if(i==n)
break;
}
if(h[i]<h[s.top()])
{
s.push(i);
timel[i].first = t;
t++;
arrayl.push_back(a[i]);
i++;
}
else
{
timel[s.top()].second = t;
t++;
arrayl.push_back(-a[s.top()]);
s.pop();
}
}
while(s.empty()==false)
{
timel[s.top()].second = t;
t++;
arrayl.push_back(-a[s.top()]);
s.pop();
}
vector <pair <int,int>> timer(n);
vector <int> arrayr;
s.push(n-1);
t = 1;
timer[n-1].first = t;
t++;
arrayr.push_back(0);
arrayr.push_back(a[n-1]);
i = n-2;
while(i>=0)
{
if(s.empty())
{
s.push(i);
timer[i].first = t;
t++;
arrayr.push_back(a[i]);
i--;
if(i==0)
break;
}
if(h[i]<h[s.top()])
{
s.push(i);
timer[i].first = t;
t++;
arrayr.push_back(a[i]);
i--;
}
else
{
timer[s.top()].second = t;
t++;
arrayr.push_back(-a[s.top()]);
s.pop();
}
}
while(s.empty()==false)
{
timer[s.top()].second = t;
t++;
arrayr.push_back(-a[s.top()]);
s.pop();
}
vector <long long int> bitr(arrayr.size(),0);
vector <long long int> bitl(arrayl.size(),0);
for(int i=1;i<arrayl.size();i++)
{
bitl = update(i,arrayl[i],bitl, arrayl.size()-1);
bitr = update(i,arrayr[i],bitr, arrayr.size()-1);
}
for(int i=0;i<q;i++)
{
int type;
cin>>type;
if(type==2)
{
int s,d;
cin>>s>>d;
s--;
d--;
int x = s;
int y = d;
if(s>d)
{
while (Pl[x] != Pl[y])
{
if (x < y)
x = Pl[x];
else
y = Pl[y];
}
if(x != s)
{
cout<<-1<<endl;
}
else
{
long long int ans = getsum(timer[s].first,timer[d].first,bitr);
cout<<ans<<endl;
}
}
else
{
while (Pr[x] != Pr[y])
{
if (x > y)
x = Pr[x];
else
y = Pr[y];
}
if(y != s)
{
cout<<-1<<endl;
}
else
{
long long int ans = getsum(timel[s].first,timel[d].first,bitl);
cout<<ans<<endl;
}
}
}
else
{
int s,k;
cin>>s>>k;
long long int val = k-a[s-1];
bitl = update(timel[s-1].first,val,bitl,arrayl.size()-1);
bitl = update(timel[s-1].second,-val,bitl,arrayl.size()-1);
bitr = update(timer[s-1].first,val,bitr,arrayr.size()-1);
bitr = update(timer[s-1].second,-val,bitr,arrayr.size()-1);
a[s-1] = k;
}
}
return 0;
}
サンプル入力:
5 6
3 1 4 1 5
1 2 4 8 16
2 5 2
1 3 5
2 3 4
2 1 4
2 5 1
2 3 3
サンプル出力:
22
13
-1
22
5
フェンウィック ツリーを実装して、ツリーのパス上のノードの値の合計を計算するこの質問を試みています。フェンウィック ツリーは DFS 配列に実装されており、「イン」時間中はノード値を正として、「アウト」時間中はノード値を負として格納します [(参照されたアルゴリズムへのリンク)](https://codeforces.com/blog/entry /78564)。
h[i] > h[j] (高さ) の場合、ノード i からノード j へのエッジがあり、方向を変えるエッジは存在しません。つまり、i の増加または減少にエッジを追加する必要があります。各ノードの値はベクトル a に格納され、更新できます。だから私は両方向から2本の木を構築しました。
プログラムは、サンプル テスト ケースに対して適切に実行されます。しかし、制約 N, Q <= 1000 でも TLE が得られます。この問題の元の制約は N, Q <= 2*10 5です。
Pl ベクトルは、左から右に根を張るツリーの親を格納します。Pr は、右から左に根ざしたツリーの親を格納します。同様に、arrayl と arrayr (DFS 配列)、timer と timel (開始時刻と終了時刻の配列) を作成しました。
クエリには 2 つのタイプ
があります。パスが存在するかどうかを尋ねてから、ノードの最大合計を見つけます。
または、特定のノードの値を更新します。
プログラムの順序を計算すると、O((N+Q)logN)程度になりました。私が間違っている？コードのどこが間違っていますか?
参考文献:動的計画法
を必要とする山登り問題
https://www.geeksforgeeks.org/next-greater-element/
さらに説明が必要な場合は、コメントを追加してください。関連情報を可能な限り掲載しました。