#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
我正在尝试这个问题，我已经实现了一个 Fenwick 树来计算树路径上节点值的总和。Fenwick 树已在 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（开始和结束时间数组）。
查询有两种类型：
询问是否存在路径，然后找到最大节点和。
或者更新某个节点的值。
我计算出程序的顺序大约为O((N+Q)logN)。我错了吗？我在代码中哪里出错了？
参考：
需要动态编程的爬山问题
https://www.geeksforgeeks.org/next-greater-element/
https://medium.com/@adityakumar_98609/fenwick-tree-binary-index-tree-aca7824d9c2a
在进一步澄清的情况下添加评论。我已经发布了尽可能多的相关信息。