首页 > 其他分享 >F1. Omsk Metro (simple version)

F1. Omsk Metro (simple version)

时间:2023-09-04 21:57:18浏览次数:41  
标签:F1 simple number version Omsk path 区间 station YES

F1. Omsk Metro (simple version)

This is the simple version of the problem. The only difference between the simple and hard versions is that in this version $u = 1$.

As is known, Omsk is the capital of Berland. Like any capital, Omsk has a well-developed metro system. The Omsk metro consists of a certain number of stations connected by tunnels, and between any two stations there is exactly one path that passes through each of the tunnels no more than once. In other words, the metro is a tree.

To develop the metro and attract residents, the following system is used in Omsk. Each station has its own weight $x \in \{-1, 1\}$. If the station has a weight of $-1$, then when the station is visited by an Omsk resident, a fee of $1$ burle is charged. If the weight of the station is $1$, then the Omsk resident is rewarded with $1$ burle.

Omsk Metro currently has only one station with number $1$ and weight $x = 1$. Every day, one of the following events occurs:

  • A new station with weight $x$ is added to the station with number $v_i$, and it is assigned a number that is one greater than the number of existing stations.
  • Alex, who lives in Omsk, wonders: is there a subsegment$\dagger$ (possibly empty) of the path between vertices $u$ and $v$ such that, by traveling along it, exactly $k$ burles can be earned (if $k < 0$, this means that $k$ burles will have to be spent on travel). In other words, Alex is interested in whether there is such a subsegment of the path that the sum of the weights of the vertices in it is equal to $k$. Note that the subsegment can be empty, and then the sum is equal to $0$.

You are a friend of Alex, so your task is to answer Alex's questions.

$\dagger$Subsegment — continuous sequence of elements.

Input

The first line contains a single number $t$ ($1 \leq t \leq 10^4$) — the number of test cases.

The first line of each test case contains the number $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the number of events.

Then there are $n$ lines describing the events. In the $i$-th line, one of the following options is possible:

  • First comes the symbol "+" (without quotes), then two numbers $v_i$ and $x_i$ ($x_i \in \{-1, 1\}$, it is also guaranteed that the vertex with number $v_i$ exists). In this case, a new station with weight $x_i$ is added to the station with number $v_i$.
  • First comes the symbol "?" (without quotes), and then three numbers $u_i$, $v_i$, and $k_i$ ($-n \le k_i \le n$). It is guaranteed that the vertices with numbers $u_i$ and $v_i$ exist. In this case, it is necessary to determine whether there is a subsegment (possibly empty) of the path between stations $u_i$ and $v_i$ with a sum of weights exactly equal to $k_i$. In this version of the task, it is guaranteed that $u_i = 1$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

Output

For each of Alex's questions, output "Yes" (without quotes) if the subsegment described in the condition exists, otherwise output "No" (without quotes).

You can output the answer in any case (for example, the strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive answer).

Examples

input

1
8
+ 1 -1
? 1 1 2
? 1 2 1
+ 1 1
? 1 3 -1
? 1 1 1
? 1 3 2
? 1 1 0

output

NO
YES
NO
YES
YES
YES

input

1
10
+ 1 -1
+ 1 -1
+ 3 1
+ 3 -1
+ 3 1
? 1 6 -1
? 1 6 2
? 1 2 0
? 1 5 -2
? 1 4 3

output

YES
NO
YES
YES
NO

Note

Explanation of the first sample.

The answer to the second question is "Yes", because there is a path $1$.

In the fourth question, we can choose the $1$ path again.

In the fifth query, the answer is "Yes", since there is a path $1-3$.

In the sixth query, we can choose an empty path because the sum of the weights on it is $0$.

It is not difficult to show that there are no paths satisfying the first and third queries.

 

解题思路

  可以把点对$(u,v)$所构成的路径中的每一个点看作是一个区间中的元素,假设在所有连续子区间中,区间和的最小值是$l$,最大值是$r$,那么对于询问的$x$如果有$l \leq x \leq r$,则存在某个子区间的和为$x$。

  对我来说这个结论不太直观,总觉得$l \sim r$中可能会有某些整数不存在,下面给出证明。首先一定会存在一个和最小的子区间,对于其他的子区间,我们总是可以通过这个和最小的子区间往两端不断添加或删除元素来得到。由因为每一个元素的值不是$1$就是$-1$,因此每添加或删除一个元素得到的新的子区间的和与之前相比只会相差$1$,即子区间的和是连续变化的。所以我们总是可以通过连续变化的方式从区间和最小的子区间来得到区间和最大的子区间,因此$l \sim r$中的任意一个整数值都有相应的子区间与之对应。

  + 操作相当于往某个区间的末尾插入一个元素,因此问题就变成了如何动态维护某个区间的最大子区间和以及最小子区间和。对于最大子区间和可以类别最大连续子序列和问题。由于在这个问题中始终有$u = 1$,因此定义状态$f_1(v)$表示从$1$到$v$这条路径所对应的区间中,所有子区间和的最大值;$f_0(v)$表示从$1$到$v$这条路径所对应的区间中,以$v$为区间末端的最大区间和。因此有状态转移方程$f_0(v) = \max \{ 0, \, f_0(p_v) + x \}$,$f_1(v) = \max \{ f_1(p_v), \, f_0(v) \}$,其中$p_v$是$v$的父亲。对于最小子区间和同理可得。

  AC代码如下:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 typedef long long LL;
 5 
 6 const int N = 2e5 + 10;
 7 
 8 int f[N][2], g[N][2];
 9 
10 void solve() {
11     int n;
12     scanf("%d", &n);
13     int m = 1;
14     f[1][0] = f[1][1] = 1;
15     g[1][0] = g[1][1] = 0;
16     while (n--) {
17         char op[5];
18         int x, y, z;
19         scanf("%s %d %d", op, &x, &y);
20         if (op[0] == '+') {
21             m++;
22             f[m][0] = max(0, f[x][0] + y);
23             f[m][1] = max(f[x][1], f[m][0]);
24             g[m][0] = min(0, g[x][0] + y);
25             g[m][1] = min(g[x][1], g[m][0]);
26         }
27         else {
28             scanf("%d", &z);
29             printf("%s\n", z >= g[y][1] && z <= f[y][1] ? "YES" : "NO");
30         }
31     }
32 }
33 
34 int main() {
35     int t;
36     scanf("%d", &t);
37     while (t--) {
38         solve();
39     }
40     
41     return 0;
42 }

 

参考资料

  Codeforces Round #881 (Div. 3) Editorial:https://codeforces.com/blog/entry/117468

标签:F1,simple,number,version,Omsk,path,区间,station,YES
From: https://www.cnblogs.com/onlyblues/p/17678175.html

相关文章

  • [CF1641D] Two Arrays
    题目描述Samchangedhisschoolandonthefirstbiologylessonhegotaveryinterestingtaskaboutgenes.Youaregiven$n$arrays,the$i$-thofthemcontains$m$differentintegers—$a_{i,1},a_{i,2},\ldots,a_{i,m}$.Alsoyouaregivenanarra......
  • Subversion权限文件AuthzSVNAccessFile示例[摘]
    Subversion权限文件AuthzSVNAccessFile示例选择自digitking的Blog  在使用Subversion时,认证文件AuthzSVNAccessFile能控制每一个目录的权限,但讲解的文档较少,中文文档更少。下面通过实例讲解使用方法。环境Windows2003Server,局域网,域:domain.com.cnApache2.0.52Subversion......
  • [CF1599A] Weights
    题目描述Youaregivenanarray$A$oflength$N$weightsofmasses$A_1$,$A_2$...$A_N$.Notwoweightshavethesamemass.Youcanputeveryweightononesideofthebalance(leftorright).Youdon'thavetoputweightsinorder$A_1$......
  • Subversion 加锁功能
    作者fbysss关键字:svn   Subversion一样可以加锁,只不过需要单独去操作。checkout不会自动加锁。在Tortoise中可以使用GetLock菜单项来操作。   如果加锁者出差了,如何打开锁呢?通过breaklock来实现。这个好像要在browse里面进行。不用担心强行解锁会如何,因为一切操作都有记......
  • [CF1854C] Expected Destruction
    题目描述Youhaveaset$S$of$n$distinctintegersbetween$1$and$m$.Eachsecondyoudothefollowingsteps:Pickanelement$x$in$S$uniformlyatrandom.Remove$x$from$S$.If$x+1\leqm$and$x+1$isnotin$S$,add$x+......
  • CF1848B Vika and the Bridge 题解
    CF1848BVikaandtheBridge题解题目大意给个题目传送门吧,感觉题意已经很清楚了题目传送门分析(我不会告诉你我第一眼看过去是二分)因为我们只能改一块木板的颜色,所以可以考虑贪心。大概算了下复杂度,也没有问题。题解我们要去求每种颜色最大距离的最小值,那我们可以先去求......
  • CF163E e-Government
    给定\(k\)个字符串\(t\),一个字符串集合\(S\)与\(n\)次操作,初始时\(S\)为空。操作有三个类型:将指定编号的字符串加入\(S\)中;将指定编号的字符串从\(S\)中删除;给定字符串\(s\),询问\(S\)中所有字符串在\(s\)中的匹配次数之和。\(n,k\le10^5\),\(\sum\lef......
  • vue --version 运行出现throw new ERR_SYSTEM_ERROR 错误
    (1)根据错误提示信息,找到出错入口文件:E:\SVN\zlpt\node_modules\node-ipc\entities\Defaults.js然后指定位置添加如下代码即可:constos=require('os');os.hostname=()=>"localhost";......
  • 【题解】Educational Codeforces Round 153(CF1860)
    每次打都想感叹一句,Educational名不虚传。A.NotaSubstring题目描述:有\(t\)组数据,对于每一组数据,你需要判断能否构造一个只由左右括号组成且长度为已经给定字符串的\(2\)倍且已经给定的字符串不是子串的合法字符串。注:合法的字符串是左右括号能完全匹配的字符串。如果能,......
  • CF1863C 题解
    CF1863CMEXRepetition题解Links洛谷CodeforcesDescription给你一个长度为\(n\)的序列\(a\),满足\(\foralli\in[1,n]\),\(0\leqa_{i}\leqn\)且序列中的数互不相同。定义一次操作为:按照\(i\)从\(1\)到\(n\)的顺序,\(a_{i}\gets\operatorname{MEX}(a_{1}......