*[contest:446860]*↵
↵
Hello everyone!↵
↵
Thank you all for participating in this contest!!↵
↵
*Congratulations to all the winners and the participants.*↵
↵
Also thanks to [user:Kavish_Shah,2023-05-08], [user:Manav_7603,2023-05-08], [user:Keyagohil,2024-01-01] , [user:Mulya_patel,2024-01-01] and [user:rudrashah,2024-01-01] for helping in creating the contest.↵
↵
*Make sure to upsolve all the questions.* ↵
↵
[problem:1866A]↵
↵
<spoiler summary="Explanation">↵
In order to have the product of all elements be 0, at least one element must be 0. For each element Ai, the minimum number of perations to turn it into 0 is |Ai|. Therefore, the minimum number of operations to turn at least one element into 0 is the minimum value of |Ai| out of all elements.↵
↵
Time complexity: O(N)↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
int main() {↵
int n;↵
cin>>n;↵
int a[n],b[n];↵
for(int i=0;i<n;i++)↵
{↵
cin>>a[i];↵
}↵
for(int j=0;j<n;j++)↵
{↵
b[j]=abs(a[j]);↵
}↵
sort(b,b+n);↵
if(b[0]==0)↵
{↵
cout<<0<<endl;↵
}↵
else↵
{↵
cout<<b[0]<<endl;↵
}↵
↵
return 0;↵
}↵
~~~↵
</spoiler>↵
↵
[problem:1451B]↵
↵
<spoiler summary="Explanation">↵
The condition stated above is both necessary and sufficient.↵
↵
Proof that it is necessary:↵
↵
Assume that a non-contiguous subsequence exists when the condition is false. If the first character of the substring is the first occurrence of its kind, then the subsequence cannot start before it. Similarly, if the last character of the substring is the last occurrence of its kind, then the subsequence cannot end after it. In such a case, the only subsequence that is of the same length as the given substring and equal to it, is the substring itself. However, this subsequence is contiguous — which is a contradiction.↵
↵
Thus, it is a necessary condition.↵
↵
Proof that it is sufficient:↵
↵
If the first character of the substring s[li...ri]↵
occurs at some index j↵
(j<li)↵
, then the subsequence sjsli+1...sri↵
is good.↵
↵
If the last character of the substring s[li...ri]↵
occurs at some index j↵
(j>ri)↵
, then the subsequence sli...sri−1sj↵
is good.↵
↵
Thus it is sufficient.↵
↵
Time complexity: O(nq)↵
or O(n+q)↵
for each case depending on implementation.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
int32_t main() {↵
ios::sync_with_stdio(0); cin.tie(0);↵
int t;↵
cin >> t;↵
while(t--) {↵
int i, n, Q; string s;↵
cin >> n >> Q >> s;↵
while(Q--) {↵
int l, r; cin >> l >> r; --l; --r;↵
bool bad = true;↵
for(i = 0; i < l and bad; i++)↵
if(s[i] == s[l]) bad = false;↵
for(i = r+1; i < n and bad; i++)↵
if(s[i] == s[r]) bad = false;↵
cout << (bad? "NO" : "YES") << '\n';↵
}↵
}↵
return 0;↵
}↵
~~~↵
↵
</spoiler>↵
↵
[problem:1557B]↵
↵
<spoiler summary="Explanation">↵
This problem can be solved for \textbf{at least} k↵
subarrays as it is easy to just add extra subarrays (if needed) to achieve \textbf{exactly} k↵
subarrays. To solve this problem, you need to know what are the numbers that can be grouped into the same subarray. This can be done by maintaining the sorted array along with the non-sorted array.↵
↵
As the numbers are distinct, we can iterate over the non-sorted array, and just add each element ai↵
to the subarray ending in ai−1↵
IFF they follow each other in the sorted array, or start a new subarray if they do not follow each other.↵
↵
For example, if the (non-sorted) array is [↵
2↵
, 3↵
, −1↵
, 1↵
], the sorted array will be [↵
−1↵
, 1↵
, 2↵
, 3↵
]↵
. If we iterate over the non-sorted array, we will add 2↵
to a new subarray, then we will add 3↵
to the same subarray as they follow each other in the sorted array. After that, we will start a new subarray at −1↵
as −1↵
and 3↵
do not follow each other in the sorted array. Finally, we will add 1↵
to the subarray containing −1↵
. It should end up like this: { [↵
2↵
, 3↵
]↵
, [↵
−1↵
, 1↵
]↵
}.↵
↵
Using this approach, you can get the smallest number of subarrays needed. If it is strictly greater than the given k↵
, the answer is ''NO''. Otherwise, it is ''YES''.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define endl "\n"↵
void run() {↵
ios::sync_with_stdio(false);↵
cin.tie(NULL);↵
cout.tie(NULL);↵
#ifndef ONLINE_JUDGE↵
freopen("input.txt", "r", stdin);↵
#else↵
#endif↵
}↵
↵
↵
int main() {↵
run();↵
int t;↵
cin >> t;↵
while (t--) {↵
int n, k;↵
cin >> n >> k;↵
vector<pair<int, int>> v(n);↵
for (int i = 0; i < n; i++) {↵
cin >> v[i].first;↵
v[i].second = i;↵
}↵
sort(v.begin(), v.end());↵
int ans = 1;↵
for (int i = 1; i < n; i++)↵
if (v[i - 1].second + 1 != v[i].second)↵
ans++;↵
cout << (ans <= k ? "YES" : "NO") << endl;↵
}↵
}↵
~~~↵
</spoiler>↵
↵
[problem:1389C]↵
↵
<spoiler summary="Explanation">↵
Let's analyze when the string is good. Suppose it is t1t2…tk↵
.↵
↵
The cyclic shifts of this string are tkt1t2…tk−1↵
and t2t3…tkt1↵
. We get the following constraints for a good string: tk=t2↵
, t1=t3↵
, t2=t4↵
, ..., tk−2=tk↵
, tk−1=t1↵
. If the string has odd length, then all characters should be equal to each other; otherwise, all characters on odd positions should be equal, and all characters on even positions should be equal.↵
↵
Now, since there are only 10↵
different types of characters, we can brute force all possible combinations of the first and the second character of the string we want to obtain (there are only 100↵
of them) and, for each combination, greedily construct the longest possible subsequence of s↵
beginning with those characters in O(n).↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
#define sz(a) int((a).size())↵
#define forn(i, n) for (int i = 0; i < int(n); ++i)↵
↵
int solve(const string& s, int x, int y) {↵
int res = 0;↵
for (auto c : s) if (c - '0' == x) {↵
++res;↵
swap(x, y);↵
}↵
if (x != y && res % 2 == 1)↵
--res;↵
return res;↵
}↵
↵
void solve() {↵
string s;↵
cin >> s;↵
int ans = 0;↵
forn(x, 10) forn(y, 10)↵
ans = max(ans, solve(s, x, y));↵
cout << sz(s) - ans << endl;↵
}↵
↵
int main() {↵
int T;↵
cin >> T;↵
while (T--) solve();↵
}↵
~~~↵
↵
</spoiler>↵
↵
[problem:283B]↵
↵
<spoiler summary="Explanation">↵
First, suppose we only have the sequence a2, a3, …an. We note that the current state is only determined by the location and the direction we are facing, so there are only 2·(n - 1) states total. Then, we can use DFS with memorization to find the distance traveled from each state, or - 1 if a cycle is formed, in O(n) time. Now, when we add a1 into the sequence, we essentially only need to give the distance traveled starting from each state facing left. The only difference is that if we ever land on a1 again, there must be a cycle, as we started on a1. Using this, we can solve the problem in O(n) time total.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
↵
~~~↵
#include <iostream>↵
using namespace std;↵
typedef long long LL;↵
const LL M=200200;↵
LL n,a[M],b[M][2],c[M][2],d;↵
LL go(LL i,LL j){↵
if(i<1||i>n)return 0;↵
LL& r=b[i][j],&s=c[i][j];↵
if(1==i||s==d)r=-1;↵
else if(!s){↵
s=d;↵
LL t=go(i+(j?-a[i]:a[i]),!j);↵
r=t<0?-1:t+a[i];↵
}↵
return r;↵
}↵
int main(){↵
cin>>n;↵
for(LL i=2;i<=n;++i)cin>>a[i];↵
for(LL i=1,t;i<n;++i)++d,cout<<((t=go(i+1,1))<0?-1:t+i)<<endl;↵
}↵
~~~↵
↵
</spoiler>↵
↵
[problem:384C]↵
↵
<spoiler summary="Explanation">↵
This is kind of task that needs to be break into smaller subproblems that you can solve independently, then put them together and get solution.↵
↵
Let’s define level of a node the number of edges in the path from root to the node. Root (node 1) is at level 0, sons of root are at level 1, sons of sons of root are at level 2 and so on.↵
↵
Now suppose you want to do an operation of type 1 to a node x. What nodes from subtree of x will be added +val (a positive value)? Obviously, x will be first, being located at level L. Sons of x, located at level L + 1 will be added –val. Sons of sons, located at level L + 2, will be added value +val again. So, nodes from subtree of x located at levels L, L + 2, L + 4, ... will be added a +val, and nodes located at levels L + 1, L + 3, L + 5 will be added a –val. Let’s take those values of L modulo 2. All nodes having remainder L modulo 2 will be added a +val, and nodes having reminder (L + 1) modulo 2 will be added –val. In other words, for a fixed x, at a level L, let y a node from subtree of x, at level L2. If L and L2 have same parity, +val will be added to y. Otherwise, -val will be added to y.↵
↵
From here we have the idea to split nodes of tree in 2 sets – those being located at even level and those being located at odd level. What still makes the problem hard to solve? The fact that we have a tree. If nodes from a subtree would be a contiguous sequence instead of some nodes from a tree, problem would be simpler: the problem would reduce to add / subtract values to all elements of a subarray and query about a current value of an element of array. So, how can we transform tree to an array, such as for a node x, all nodes from subtree of x to be a subarray of array?↵
↵
The answer is yes. We can do this by properties of DFS search. Before reading on, make sure that you know what is discovery time and finish time in a DFS search. Let’s build 3 arrays now – discover[], representing nodes in order of their discover times (a node is as before in discover as it has a small discover time), begin[] = for a node, in which time it was discovered and end[] = what’s last time of a discovered node before this node finishes. For a subtree of x, all nodes in the subtree are nodes in discover from position begin[x] to end[x].↵
↵
Example: suppose you have tree 1-5; 1-6; 6-7; 6-4; 4-2; 4-3↵
↵
Discover is {1, 5, 6, 7, 4, 2, 3}.↵
↵
begin is {1, 6, 7, 5, 2, 3, 4}.↵
↵
end is {7, 6, 7, 7, 2, 7, 4}.↵
↵
What’s subtree of node 6? elements of discover from position begin[6] to end[6]. In this case, from 3 to 7, so elements {6, 7, 4, 2, 3}. You can see it’s correct and take more examples if you want :)↵
↵
Now, we reduced problem to: you’re given an array A. you can perform 2 operations:↵
↵
1/ increase all elements from a range [x, y] to a value val (val can be negative, to treat subtractions)↵
↵
2/ what’s current value of an element from position pos.↵
↵
Those who solved “Iahub and Xors” from my last round, CF 198, should probably say they saw something similar before. If you didn’t solve problem before, I encourage you to do it after you solve this one, it uses a similar idea to what will follow now. Also, if you don’t know Fenwick trees, please read them before moving on. An alternative would be for this task using segment trees with lazy update, but I see this one more complicated than needed.↵
↵
I’ll use now a not so common approach when dealing with data structures. Instead of keeping in a node the result, like you usually do, I’ll keep just an auxiliary information. So what algorithm proposed does:↵
↵
Let A an array, initially with all elements 0.↵
↵
When you need to update range [x, y] with value val, you simply do A[x] += val and A[y + 1] -= val.↵
↵
When you need to answer a query about position pos, you output A[1] + A[2] + ... + A[pos].↵
↵
Implemented brute force, you get O(1) per update and O(N) per query. However, these both are operations supported by a Fenwick tree, so you can get O(logN) per operation.↵
↵
It may not be very clear why this algorithm works. Let’s take a closer look: an update needs to add value val only to range [x, y]. When you query a position pos, let’s see if algorithm handles it correctly:↵
↵
1/ pos < x. In this case, result must not be affected by my update. Since pos < x and I only updated 2 values with indices >= x, when doing A[1] + A[2] + ... + A[pos] it won’t matter at all I did that update – at least not for this query.↵
↵
2/ x <= pos <= y. Here, for a pos, I need to add value val only once. We add it only at A[x] – in this way it will be counted once, and it will be considered for each elements from range [x, y] (since an element at position p from range [x, y] has p >= x, in A[1] + A[2] + ... + A[p] I’ll have to consider A[x]).↵
↵
3/ pos > y. Here I don’t have to consider the query. But it would be considered when processing A[x]. But if I add to A[y + 1] value –val I’ll just cancel the value previously added.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
↵
~~~↵
#include"bits/stdc++.h"↵
using namespace std;↵
const int N=2e5+10;↵
int a[N],in[N],out[N],tnow,tree[2*N],n,m,vis[N],lev[N];↵
vector<int> g[N];↵
void upd(int id, int val){↵
for(;id<2*N;id+=id&-id)tree[id]+=val;↵
}↵
int get(int id){↵
int sum=0;↵
for(;id>=1;id-=id&-id)sum+=tree[id];↵
return sum;↵
}↵
void dfs(int u){↵
vis[u]=1;↵
in[u]=++tnow;↵
for(auto v:g[u]){↵
if(!vis[v]){↵
lev[v]=lev[u]+1;↵
dfs(v);↵
}↵
}↵
out[u]=++tnow;↵
↵
}↵
signed main(){↵
cin>>n>>m;↵
for(int i=1;i<=n;i++)cin>>a[i];↵
for(int i=1,u,v;i<n;i++){↵
cin>>u>>v;↵
g[u].push_back(v);↵
g[v].push_back(u);↵
}↵
dfs(1);↵
↵
while(m--){↵
int ch;↵
cin>>ch;↵
if(ch==1){↵
int u,val;↵
cin>>u>>val;↵
↵
if(lev[u]%2){↵
upd(in[u],-val);↵
upd(out[u],val);↵
}↵
else{↵
upd(in[u],val);↵
upd(out[u],-val);↵
}↵
}↵
else{↵
int u;cin>>u;↵
if(lev[u]%2==0){↵
cout<<a[u]+get(in[u])<<"\n";↵
}↵
else cout<<a[u]-get(in[u])<<"\n";↵
}↵
}↵
}↵
↵
~~~↵
↵
</spoiler>↵
↵
Feel free to ask about any doubt in the above mentioned questions and their solutions.↵
↵
*~ See you soon in the next contest, till then Happy learning!! Happy coding!!*↵
↵
*Team CSI.*
↵
Hello everyone!↵
↵
Thank you all for participating in this contest!!↵
↵
*Congratulations to all the winners and the participants.*↵
↵
Also thanks to [user:Kavish_Shah,2023-05-08], [user:Manav_7603,2023-05-08], [user:Keyagohil,2024-01-01] , [user:Mulya_patel,2024-01-01] and [user:rudrashah,2024-01-01] for helping in creating the contest.↵
↵
*Make sure to upsolve all the questions.* ↵
↵
[problem:1866A]↵
↵
<spoiler summary="Explanation">↵
In order to have the product of all elements be 0, at least one element must be 0. For each element Ai, the minimum number of perations to turn it into 0 is |Ai|. Therefore, the minimum number of operations to turn at least one element into 0 is the minimum value of |Ai| out of all elements.↵
↵
Time complexity: O(N)↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
int main() {↵
int n;↵
cin>>n;↵
int a[n],b[n];↵
for(int i=0;i<n;i++)↵
{↵
cin>>a[i];↵
}↵
for(int j=0;j<n;j++)↵
{↵
b[j]=abs(a[j]);↵
}↵
sort(b,b+n);↵
if(b[0]==0)↵
{↵
cout<<0<<endl;↵
}↵
else↵
{↵
cout<<b[0]<<endl;↵
}↵
↵
return 0;↵
}↵
~~~↵
</spoiler>↵
↵
[problem:1451B]↵
↵
<spoiler summary="Explanation">↵
The condition stated above is both necessary and sufficient.↵
↵
Proof that it is necessary:↵
↵
Assume that a non-contiguous subsequence exists when the condition is false. If the first character of the substring is the first occurrence of its kind, then the subsequence cannot start before it. Similarly, if the last character of the substring is the last occurrence of its kind, then the subsequence cannot end after it. In such a case, the only subsequence that is of the same length as the given substring and equal to it, is the substring itself. However, this subsequence is contiguous — which is a contradiction.↵
↵
Thus, it is a necessary condition.↵
↵
Proof that it is sufficient:↵
↵
If the first character of the substring s[li...ri]↵
occurs at some index j↵
(j<li)↵
, then the subsequence sjsli+1...sri↵
is good.↵
↵
If the last character of the substring s[li...ri]↵
occurs at some index j↵
(j>ri)↵
, then the subsequence sli...sri−1sj↵
is good.↵
↵
Thus it is sufficient.↵
↵
Time complexity: O(nq)↵
or O(n+q)↵
for each case depending on implementation.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
int32_t main() {↵
ios::sync_with_stdio(0); cin.tie(0);↵
int t;↵
cin >> t;↵
while(t--) {↵
int i, n, Q; string s;↵
cin >> n >> Q >> s;↵
while(Q--) {↵
int l, r; cin >> l >> r; --l; --r;↵
bool bad = true;↵
for(i = 0; i < l and bad; i++)↵
if(s[i] == s[l]) bad = false;↵
for(i = r+1; i < n and bad; i++)↵
if(s[i] == s[r]) bad = false;↵
cout << (bad? "NO" : "YES") << '\n';↵
}↵
}↵
return 0;↵
}↵
~~~↵
↵
</spoiler>↵
↵
[problem:1557B]↵
↵
<spoiler summary="Explanation">↵
This problem can be solved for \textbf{at least} k↵
subarrays as it is easy to just add extra subarrays (if needed) to achieve \textbf{exactly} k↵
subarrays. To solve this problem, you need to know what are the numbers that can be grouped into the same subarray. This can be done by maintaining the sorted array along with the non-sorted array.↵
↵
As the numbers are distinct, we can iterate over the non-sorted array, and just add each element ai↵
to the subarray ending in ai−1↵
IFF they follow each other in the sorted array, or start a new subarray if they do not follow each other.↵
↵
For example, if the (non-sorted) array is [↵
2↵
, 3↵
, −1↵
, 1↵
], the sorted array will be [↵
−1↵
, 1↵
, 2↵
, 3↵
]↵
. If we iterate over the non-sorted array, we will add 2↵
to a new subarray, then we will add 3↵
to the same subarray as they follow each other in the sorted array. After that, we will start a new subarray at −1↵
as −1↵
and 3↵
do not follow each other in the sorted array. Finally, we will add 1↵
to the subarray containing −1↵
. It should end up like this: { [↵
2↵
, 3↵
]↵
, [↵
−1↵
, 1↵
]↵
}.↵
↵
Using this approach, you can get the smallest number of subarrays needed. If it is strictly greater than the given k↵
, the answer is ''NO''. Otherwise, it is ''YES''.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define endl "\n"↵
void run() {↵
ios::sync_with_stdio(false);↵
cin.tie(NULL);↵
cout.tie(NULL);↵
#ifndef ONLINE_JUDGE↵
freopen("input.txt", "r", stdin);↵
#else↵
#endif↵
}↵
↵
↵
int main() {↵
run();↵
int t;↵
cin >> t;↵
while (t--) {↵
int n, k;↵
cin >> n >> k;↵
vector<pair<int, int>> v(n);↵
for (int i = 0; i < n; i++) {↵
cin >> v[i].first;↵
v[i].second = i;↵
}↵
sort(v.begin(), v.end());↵
int ans = 1;↵
for (int i = 1; i < n; i++)↵
if (v[i - 1].second + 1 != v[i].second)↵
ans++;↵
cout << (ans <= k ? "YES" : "NO") << endl;↵
}↵
}↵
~~~↵
</spoiler>↵
↵
[problem:1389C]↵
↵
<spoiler summary="Explanation">↵
Let's analyze when the string is good. Suppose it is t1t2…tk↵
.↵
↵
The cyclic shifts of this string are tkt1t2…tk−1↵
and t2t3…tkt1↵
. We get the following constraints for a good string: tk=t2↵
, t1=t3↵
, t2=t4↵
, ..., tk−2=tk↵
, tk−1=t1↵
. If the string has odd length, then all characters should be equal to each other; otherwise, all characters on odd positions should be equal, and all characters on even positions should be equal.↵
↵
Now, since there are only 10↵
different types of characters, we can brute force all possible combinations of the first and the second character of the string we want to obtain (there are only 100↵
of them) and, for each combination, greedily construct the longest possible subsequence of s↵
beginning with those characters in O(n).↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
#define sz(a) int((a).size())↵
#define forn(i, n) for (int i = 0; i < int(n); ++i)↵
↵
int solve(const string& s, int x, int y) {↵
int res = 0;↵
for (auto c : s) if (c - '0' == x) {↵
++res;↵
swap(x, y);↵
}↵
if (x != y && res % 2 == 1)↵
--res;↵
return res;↵
}↵
↵
void solve() {↵
string s;↵
cin >> s;↵
int ans = 0;↵
forn(x, 10) forn(y, 10)↵
ans = max(ans, solve(s, x, y));↵
cout << sz(s) - ans << endl;↵
}↵
↵
int main() {↵
int T;↵
cin >> T;↵
while (T--) solve();↵
}↵
~~~↵
↵
</spoiler>↵
↵
[problem:283B]↵
↵
<spoiler summary="Explanation">↵
First, suppose we only have the sequence a2, a3, …an. We note that the current state is only determined by the location and the direction we are facing, so there are only 2·(n - 1) states total. Then, we can use DFS with memorization to find the distance traveled from each state, or - 1 if a cycle is formed, in O(n) time. Now, when we add a1 into the sequence, we essentially only need to give the distance traveled starting from each state facing left. The only difference is that if we ever land on a1 again, there must be a cycle, as we started on a1. Using this, we can solve the problem in O(n) time total.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
↵
~~~↵
#include <iostream>↵
using namespace std;↵
typedef long long LL;↵
const LL M=200200;↵
LL n,a[M],b[M][2],c[M][2],d;↵
LL go(LL i,LL j){↵
if(i<1||i>n)return 0;↵
LL& r=b[i][j],&s=c[i][j];↵
if(1==i||s==d)r=-1;↵
else if(!s){↵
s=d;↵
LL t=go(i+(j?-a[i]:a[i]),!j);↵
r=t<0?-1:t+a[i];↵
}↵
return r;↵
}↵
int main(){↵
cin>>n;↵
for(LL i=2;i<=n;++i)cin>>a[i];↵
for(LL i=1,t;i<n;++i)++d,cout<<((t=go(i+1,1))<0?-1:t+i)<<endl;↵
}↵
~~~↵
↵
</spoiler>↵
↵
[problem:384C]↵
↵
<spoiler summary="Explanation">↵
This is kind of task that needs to be break into smaller subproblems that you can solve independently, then put them together and get solution.↵
↵
Let’s define level of a node the number of edges in the path from root to the node. Root (node 1) is at level 0, sons of root are at level 1, sons of sons of root are at level 2 and so on.↵
↵
Now suppose you want to do an operation of type 1 to a node x. What nodes from subtree of x will be added +val (a positive value)? Obviously, x will be first, being located at level L. Sons of x, located at level L + 1 will be added –val. Sons of sons, located at level L + 2, will be added value +val again. So, nodes from subtree of x located at levels L, L + 2, L + 4, ... will be added a +val, and nodes located at levels L + 1, L + 3, L + 5 will be added a –val. Let’s take those values of L modulo 2. All nodes having remainder L modulo 2 will be added a +val, and nodes having reminder (L + 1) modulo 2 will be added –val. In other words, for a fixed x, at a level L, let y a node from subtree of x, at level L2. If L and L2 have same parity, +val will be added to y. Otherwise, -val will be added to y.↵
↵
From here we have the idea to split nodes of tree in 2 sets – those being located at even level and those being located at odd level. What still makes the problem hard to solve? The fact that we have a tree. If nodes from a subtree would be a contiguous sequence instead of some nodes from a tree, problem would be simpler: the problem would reduce to add / subtract values to all elements of a subarray and query about a current value of an element of array. So, how can we transform tree to an array, such as for a node x, all nodes from subtree of x to be a subarray of array?↵
↵
The answer is yes. We can do this by properties of DFS search. Before reading on, make sure that you know what is discovery time and finish time in a DFS search. Let’s build 3 arrays now – discover[], representing nodes in order of their discover times (a node is as before in discover as it has a small discover time), begin[] = for a node, in which time it was discovered and end[] = what’s last time of a discovered node before this node finishes. For a subtree of x, all nodes in the subtree are nodes in discover from position begin[x] to end[x].↵
↵
Example: suppose you have tree 1-5; 1-6; 6-7; 6-4; 4-2; 4-3↵
↵
Discover is {1, 5, 6, 7, 4, 2, 3}.↵
↵
begin is {1, 6, 7, 5, 2, 3, 4}.↵
↵
end is {7, 6, 7, 7, 2, 7, 4}.↵
↵
What’s subtree of node 6? elements of discover from position begin[6] to end[6]. In this case, from 3 to 7, so elements {6, 7, 4, 2, 3}. You can see it’s correct and take more examples if you want :)↵
↵
Now, we reduced problem to: you’re given an array A. you can perform 2 operations:↵
↵
1/ increase all elements from a range [x, y] to a value val (val can be negative, to treat subtractions)↵
↵
2/ what’s current value of an element from position pos.↵
↵
Those who solved “Iahub and Xors” from my last round, CF 198, should probably say they saw something similar before. If you didn’t solve problem before, I encourage you to do it after you solve this one, it uses a similar idea to what will follow now. Also, if you don’t know Fenwick trees, please read them before moving on. An alternative would be for this task using segment trees with lazy update, but I see this one more complicated than needed.↵
↵
I’ll use now a not so common approach when dealing with data structures. Instead of keeping in a node the result, like you usually do, I’ll keep just an auxiliary information. So what algorithm proposed does:↵
↵
Let A an array, initially with all elements 0.↵
↵
When you need to update range [x, y] with value val, you simply do A[x] += val and A[y + 1] -= val.↵
↵
When you need to answer a query about position pos, you output A[1] + A[2] + ... + A[pos].↵
↵
Implemented brute force, you get O(1) per update and O(N) per query. However, these both are operations supported by a Fenwick tree, so you can get O(logN) per operation.↵
↵
It may not be very clear why this algorithm works. Let’s take a closer look: an update needs to add value val only to range [x, y]. When you query a position pos, let’s see if algorithm handles it correctly:↵
↵
1/ pos < x. In this case, result must not be affected by my update. Since pos < x and I only updated 2 values with indices >= x, when doing A[1] + A[2] + ... + A[pos] it won’t matter at all I did that update – at least not for this query.↵
↵
2/ x <= pos <= y. Here, for a pos, I need to add value val only once. We add it only at A[x] – in this way it will be counted once, and it will be considered for each elements from range [x, y] (since an element at position p from range [x, y] has p >= x, in A[1] + A[2] + ... + A[p] I’ll have to consider A[x]).↵
↵
3/ pos > y. Here I don’t have to consider the query. But it would be considered when processing A[x]. But if I add to A[y + 1] value –val I’ll just cancel the value previously added.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
↵
~~~↵
#include"bits/stdc++.h"↵
using namespace std;↵
const int N=2e5+10;↵
int a[N],in[N],out[N],tnow,tree[2*N],n,m,vis[N],lev[N];↵
vector<int> g[N];↵
void upd(int id, int val){↵
for(;id<2*N;id+=id&-id)tree[id]+=val;↵
}↵
int get(int id){↵
int sum=0;↵
for(;id>=1;id-=id&-id)sum+=tree[id];↵
return sum;↵
}↵
void dfs(int u){↵
vis[u]=1;↵
in[u]=++tnow;↵
for(auto v:g[u]){↵
if(!vis[v]){↵
lev[v]=lev[u]+1;↵
dfs(v);↵
}↵
}↵
out[u]=++tnow;↵
↵
}↵
signed main(){↵
cin>>n>>m;↵
for(int i=1;i<=n;i++)cin>>a[i];↵
for(int i=1,u,v;i<n;i++){↵
cin>>u>>v;↵
g[u].push_back(v);↵
g[v].push_back(u);↵
}↵
dfs(1);↵
↵
while(m--){↵
int ch;↵
cin>>ch;↵
if(ch==1){↵
int u,val;↵
cin>>u>>val;↵
↵
if(lev[u]%2){↵
upd(in[u],-val);↵
upd(out[u],val);↵
}↵
else{↵
upd(in[u],val);↵
upd(out[u],-val);↵
}↵
}↵
else{↵
int u;cin>>u;↵
if(lev[u]%2==0){↵
cout<<a[u]+get(in[u])<<"\n";↵
}↵
else cout<<a[u]-get(in[u])<<"\n";↵
}↵
}↵
}↵
↵
~~~↵
↵
</spoiler>↵
↵
Feel free to ask about any doubt in the above mentioned questions and their solutions.↵
↵
*~ See you soon in the next contest, till then Happy learning!! Happy coding!!*↵
↵
*Team CSI.*
