Ссылка на Code Pastebin
#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 * 1021 * 13
-1
22 * 1024 * 5
Я пытаюсь ответить на этот вопрос, когда я реализовал дерево Фенвика для вычисления суммы значений узлов на путь дерева. Дерево Фенвика было реализовано в массиве DFS, который сохраняет значение узла как положительное в течение времени «входа» и отрицательное в течение времени «выхода» [(Ссылка на упомянутый алгоритм)] (
https://codeforces.com/blog/entry/78564).
Существует ребро от узла i к узлу j, если h [i]> h [j] (высоты) и не может быть ребер, которые меняют направление, т.е. ребра должны добавляться либо при увеличении, либо при уменьшении i. Значения каждого узла хранятся в векторе a и могут быть обновлены. Итак, я построил 2 дерева с обоих направлений.
Изображение входного образца и края образца
Программа хорошо работает для примеров тестовых случаев. Но он дает TLE даже при ограничениях N, Q <= 1000. Исходные ограничения задачи: N, Q <= 2 * 10 <sup>5
Вектор Pl хранит родительский элемент дерева укореняется слева направо. Pr хранит родительский элемент дерева с корнем справа налево. Точно так же я создал массивы и массивы (массивы DFS), таймер и таймер (массив времени начала и окончания).
Запросы бывают двух типов:
Либо спросите, существует ли путь, затем найдите максимальная сумма узлов.
Или Обновить значение определенного узла.
Я рассчитал, что порядок программы будет примерно O ((N + Q) logN) * 1046 *. Я ошибся? Где я ошибаюсь в коде?
Ссылки:
Проблема подъема на холм, требующая программирования Dynami c
https://www.geeksforgeeks.org/next-greater-element/
https://medium.com/@adityakumar_98609 / fenwick-tree-binary-index-tree-aca7824d9c2a
Добавляйте комментарии в случае дополнительных пояснений. Я разместил как можно больше актуальной информации.