水晶

题目背景

2019/12/27 修改最后一个点的数据范围 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$ 对于所有测试点，保证调用交互库消耗的时间不超过300ms ``` #include<cstdio> using namespace std; #define u32 unsigned int #define u64 unsigned long long int cl; const int N=2500007; const long long M=998244353LL; int n,q,k; int 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(); u64 bacs=s; for(int i=1;i<=n;i++){ s=s*19260817+1; a[i]=((s>>8)%ra+1); //a[i]=rand(1,ra); s=s*19260817+1; //na[i]=((s>>8)%(M-1)+1); //na[i]=rand(1,M-1); } s=bacs; for(int i=1;i<=n;i++){ s=s*19260817+1; //a[i]=((s>>8)%ra+1); //a[i]=rand(1,ra); s=s*19260817+1; na[i]=((s>>8)%(M-1)+1); //na[i]=rand(1,M-1); } bacs=s; for(int i=1;i<=n;i++){ s=s*19260817+1; b[i]=((s>>8)%ra+1); //a[i]=rand(1,ra); s=s*19260817+1; //nb[i]=((s>>8)%(M-1)+1); } s=bacs; for(int i=1;i<=n;i++){ s=s*19260817+1; //b[i]=((s>>8)%ra+1); //a[i]=rand(1,ra); s=s*19260817+1; nb[i]=((s>>8)%(M-1)+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{ s=s*19260817+1; x=((s>>8)%n+1); s=s*19260817+1; y=((s>>8)%n+1); s=s*19260817+1; z=((s>>8)%n+1); s=s*19260817+1; u=((s>>8)%n+1); //x=rand(1,n);y=rand(1,n);z=rand(1,n);u=rand(1,n); } if(k&1){ int t=lastans%n+1; if((x+=t)>n)x-=n; if((y+=t)>n)y-=n; if((z+=t)>n)z-=n; if((u+=t)>n)u-=n; /*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

输出样例 #1

输入样例 #2

输出样例 #2

输入样例 #3

输出样例 #3

输入样例 #4

输出样例 #4

输入样例 #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

说明

样例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| 2500000| 4000000| |