水晶

题目背景

Steve带领军队到达了黑暗势力的据点 然而,他发现黑暗势力正在使用水晶保护自己 为了突破防御,Steve开始用武器攻击水晶

题目描述

黑暗势力的水晶已经排成了一排,而且数量很多 水晶可分为$n$组,第$i$组内有$a_i$个水晶,并且防御力均为$na_i$ Steve的武器也已经排成了一排,而且数量也很多 武器也可分为$n$组,第$i$组内有$b_i$个武器,并且攻击力均为$nb_i$ 每一轮攻击中,黑暗势力会选择一个水晶,Steve会选择一个武器 如果这个武器的攻击力大于水晶的防御力,这次攻击就有效 然而,水晶和武器数量太多了,Steve很难知道具体选择了哪个水晶,哪个武器 现在Steve希望知道: 1.对于所有可能的情况,有多少种选法是一次有效的攻击 2.如果已经知道选用水晶的防御力在第$x$组水晶的防御力和第$y$组水晶的防御力之间,且选用武器的攻击力在第$z$组武器的攻击力和第$u$组武器的攻击力之间,那么,有多少种选法是一次有效的攻击 也就是,选择的水晶防御力不小于第$x$组水晶和第$y$组水晶防御力的较小值,不大于两者的较大值,武器同理 两个选法不同,当且仅当选用的水晶或武器不同(可以在同一组) 由于战事紧迫,你需要迅速回答问题才能让Steve作出下一轮攻击的决策 因此,部分测试点强制在线 为了避免答案过大,答案对$998244353$取模

输入输出格式

输入格式


由于输入输出规模较大,使用下面的模板完成数据生成,具体格式请看模板和样例 评测时,所有测试点都只会输入5个数,输出1个数,因此你不需要输入输出优化 为便于调试,该模板可以手动指定数据,并输出每一个询问的答案,只需要输入的$k=0$ ``` #include using namespace std; #define u32 unsigned int #define u64 unsigned long long const int N=1000007; const long long M=998244353LL; int n,q,k; u32 a[N],na[N],b[N],nb[N]; int x,y,z,u; namespace lib{ u64 read(){ u64 n=0; char c=getchar(); while(c<'0'||c>'9')c=getchar(); while(c>='0'&&c<='9'){ n=n*10+c-'0'; c=getchar(); } return n; } char r[30]; void write(u64 num){ if(num==0){ putchar('0'); return; } int t=0; while(num){ r[t++]=num%10+'0'; num/=10; } while(t)putchar(r[--t]); } u64 s; u64 rand(u64 l,u64 r){ s=s*19260817+1; return ((s>>8)%(r-l+1)+l); } int ra,t; void init(){ n=read();k=read(); if(k<2){ for(int i=1;i<=n;i++){ a[i]=read();na[i]=read(); } for(int i=1;i<=n;i++){ b[i]=read();nb[i]=read(); } }else{ s=read();ra=read(); for(int i=1;i<=n;i++){ a[i]=rand(1,ra); na[i]=rand(1,M-1); } for(int i=1;i<=n;i++){ b[i]=rand(1,ra); nb[i]=rand(1,M-1); } } q=read(); } u64 lastans; u64 res; void reply(u64 num){ if(k<2){ write(num);putchar('\n'); }else{ res=res*233+num; } lastans^=num; } void query(){ if(k<2){ x=read();y=read();z=read();u=read(); }else{ x=rand(1,n);y=rand(1,n);z=rand(1,n);u=rand(1,n); } if(k&1){ x=(x+lastans)%n+1; y=(y+lastans)%n+1; z=(z+lastans)%n+1; u=(u+lastans)%n+1; } } void stop(){ if(k>=2){write(res);putchar('\n');} } } int main(){ lib::init(); //现在你可以使用生成的a,na,b,nb //回答第一问 lib::reply(233); for(int i=1;i<=q;i++){ lib::query(); //解决并回答第二问 lib::reply(233); } lib::stop(); } ```

输出格式


如果$k=0$,则会分别输出每一问的答案 否则,只会输出一个整数用于检查结果是否正确

输入输出样例

输入样例 #1

2 0
1 1
3 3
2 2
4 4
9
1 1 1 1
1 1 1 2
1 1 2 2
2 1 1 1
1 2 1 2
1 2 2 2
2 2 1 1
2 2 1 2
2 2 2 2

输出样例 #1

18
2
6
4
2
18
16
0
12
12

输入样例 #2

2 0
1 1
2 2
2 2
3 3
9
1 1 1 1
1 1 1 2
1 1 2 2
1 2 1 1
1 2 1 2
1 2 2 2
2 2 1 1
2 2 1 2
2 2 2 2

输出样例 #2

11
2
5
3
2
11
9
0
6
6

输入样例 #3

5 0
1 1
1 1
1 1
2 1
2 1
1 1
1 1
2 1
2 1
3 1
7
2 4 1 1
1 3 3 4
3 4 5 5
2 5 4 4
1 5 5 5
1 3 1 2
1 2 3 4

输出样例 #3

11
0
6
5
6
5
0
6

输入样例 #4

3 0
3 1
2 2
1 3
4 4
5 5
6 6
12
1 3 2 2
1 2 2 3
3 1 1 2
2 1 3 1
1 1 2 3
3 1 3 1
3 2 2 3
1 2 3 3
1 2 1 3
3 2 1 1
2 2 1 3
3 3 1 2

输出样例 #4

90
30
33
54
45
11
90
55
18
45
20
30
27

输入样例 #5

3 2 233 5 10

输出样例 #5

15618218285282996994

输入样例 #6

3 0
3 754517792
1 842082509
4 600944080
2 592435186
5 348652025
5 247250863
10
1 3 3 2
3 2 1 1
2 2 3 2
2 1 2 1
3 3 3 1
2 3 3 2
1 3 3 3
1 3 3 3
2 2 1 3
2 1 2 1

输出样例 #6

988687952
712318441
204869162
71500349
703342331
285345621
783818790
712318441
712318441
276369511
703342331

说明

样例1解释: 当选择第二组武器时,一定能进行一次有效攻击 当选择第一组武器时,只有选择第一组水晶才能进行一次有效攻击 因而,不难求出每一问的答案 建议根据样例进一步理解题意 样例5与样例6一致 数据范围: 对于所有数据,满足$1\le x,y,z,u \le n$,$1\le a_i,b_i\le 10^9$,$1\le na_i,nb_i\le 998244352$ 如未特别说明,$k=3$,即:由模板生成数据,强制在线 如果$k=2$,那么这组数据仍由生成器生成,但不强制在线,也就是你可以在不回答询问的情况下得到下一个询问的真实值,随后按顺序回答即可 测试点| 分值| n | q| 特殊性质 :-: | :-: | :-: | :-: | :-: 1| 4| 100| 100| $k=2$| 2| 14| 3000| 3000| $k=2$| 3| 11| 100000| 100000| $a_i,b_i\le 100$| 4| 10| 15| 4000000| | 5| 12| 100| 4000000| | 6| 14| 5000| 4000000| | 7| 16| 100000| 100000| | 8| 19| 1000000| 4000000| |