| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 241 | 206 | 178 | 85.990% |
In the faraway country of Lineland, tech companies are starting to take over! Every week, it seems that tech companies sprout from the ground, merge, get acquired, or go under. For software engineers looking for new jobs in Lineland, it can be difficult to even find the companies where they’re interviewing.
To solve this issue, you’re going to make a new tech company! The product is simple: using deep neural blockchains in the cloud, your app finds the distance between any two tech companies in Lineland. This is supremely useful, as companies change offices all the time and it’s difficult to stay completely up to date. By centralizing this information, your company is going to make the world a better place.
Since Lineland is organized around a single line, the location of a company can be given by a single coordinate. The distance between any two companies is equal to the distance between their two coordinates.
Your job is to handle two kinds of user requests to the company’s flagship app. One kind of request updates the address of a company, the other requests the shortest distance between two companies.
The first line has two positive space-separated integers $N$ and $Q$: the number of companies the app tracks (2ドル \le N \le 100,円 000$), and the number of requests to process (1ドル \le Q \le 100,円 000$). The next line has $N$ space-separated integers 1ドル \le X_ i \le 10^9,ドル which are the initial locations of the $N$ companies, given in order from $i=1$ to $i=N$.
Each of the next $Q$ lines has 3ドル$ space-separated integers, taking one of the following forms:
1ドル$ $C$ $X,ドル which means that company $C$ moves its location to $X,ドル or
2ドル$ $A$ $B,ドル which is a query for the distance between companies $A$ and $B$.
It is guaranteed that 1ドル \leq A, B, C \leq N$ and 1ドル \leq X \leq 10^9$. It is possible two companies can share the same location. It is also guaranteed there is at least one query of type 2ドル$.
For each query of type 2ドル,ドル print the distance between companies $A$ and $B$.
5 10 5 2 8 1 4 1 2 10 2 4 5 2 1 3 1 4 3 2 1 5 2 5 2 1 4 1 2 2 4 1 3 15 2 4 1
3 3 1 6 9 4
In the first query, Company 2ドル$ moves to location 10ドル$. Then the app is asked for the distance between company 4ドル$ and company 5ドル,ドル which is 3ドル$. The next query is the distance between companies 1ドル$ and 3ドル,ドル which is also 3ドル$. A number of updates and queries follow.