P11366 [Ynoi2024] Doomsday Magical Girl Plan
Background
Description
Given a monoid with identity $(D,+,e)$, and a sequence $a_1,\dots,a_n$ consisting of elements in $D$, with all initial values being $e$, you need to support $m$ operations. Each operation is either a point update or a range sum query.
For each update operation, the number of times you use $+$ must not exceed $M_1$.
For each query operation, the number of times you use $+$ must not exceed $M_2$.
Basic properties of the monoid:
$\forall a\in D,\; e+a=a+e=a$
$\forall a,b,c\in D,\;(a+b)+c=a+(b+c)$
This is an interactive problem. You need to include the header `lib.h`, or put its content at the very beginning of your program.
The content of the provided header `lib.h` is:
```c++
struct Data{
unsigned short a,b,c,d;
};
Data operator+(Data a,Data b);
void init(int n,int k,Data d);
void update(int x,Data d);
Data query(int l,int r);
```
Here, `Data` represents $D$, and `Data operator+` represents $+$. The interactive library provides the implementation of these parts.
You need to implement:
`init`, used for initialization. Here `n,k,d` represent $n,M_2$, and the identity element $e$ of $D$, respectively. You may use $+$, but since $e+e=e$, you cannot obtain useful results from it.
`update`, which represents an update operation, setting $a_x$ to $d$.
`query`, which represents a range sum query operation, querying $a_l+a_{l+1}+\dots+a_r$. The query result should be returned as the return value.
Input Format
N/A
Output Format
N/A
Explanation/Hint
Idea: ccz181078, Solution: ccz181078, Code: ccz181078, Data: ccz181078.
For all testdata, $n=10^5,\;m=2\times 10^5$.
## Constraints
| Subtask ID | $M_1$ | $M_2$ | Score |
| ---------- | ----- | ----- | ----- |
| 1 | 4000 | 2 | 11 |
| 2 | 700 | 3 | 7 |
| 3 | 400 | 4 | 5 |
| 4 | 200 | 5 | 4 |
| 5 | 200 | 6 | 4 |
| 6 | 100 | 7 | 3 |
| 7 | 80 | 8 | 3 |
| 8 | 60 | 9 | 3 |
| 9 | 2811 | 2 | 16 |
| 10 | 542 | 3 | 11 |
| 11 | 272 | 4 | 8 |
| 12 | 137 | 5 | 7 |
| 13 | 113 | 6 | 5 |
| 14 | 75 | 7 | 5 |
| 15 | 69 | 8 | 4 |
| 16 | 48 | 9 | 4 |
The `lib\down` directory contains the provided interactive library files.
The `lib\require` directory contains the interactive library files used for judging.
The `data` directory contains the judging test points.
The `data2` directory contains the provided samples.
Translated by ChatGPT 5