#P5510. 水晶

水晶

题目背景

2019/12/27 修改最后一个点的数据范围

Steve带领军队到达了黑暗势力的据点

然而，他发现黑暗势力正在使用水晶保护自己

为了突破防御，Steve开始用武器攻击水晶

题目描述

黑暗势力的水晶已经排成了一排，而且数量很多

水晶可分为nn组，第ii组内有aia_i个水晶，并且防御力均为naina_i

Steve的武器也已经排成了一排，而且数量也很多

武器也可分为nn组，第ii组内有bib_i个武器，并且攻击力均为nbinb_i

每一轮攻击中，黑暗势力会选择一个水晶，Steve会选择一个武器

如果这个武器的攻击力大于水晶的防御力，这次攻击就有效

然而，水晶和武器数量太多了，Steve很难知道具体选择了哪个水晶，哪个武器

现在Steve希望知道：

1.对于所有可能的情况，有多少种选法是一次有效的攻击

2.如果已经知道选用水晶的防御力在第xx组水晶的防御力和第yy组水晶的防御力之间，且选用武器的攻击力在第zz组武器的攻击力和第uu组武器的攻击力之间，那么，有多少种选法是一次有效的攻击

也就是，选择的水晶防御力不小于第xx组水晶和第yy组水晶防御力的较小值，不大于两者的较大值，武器同理

两个选法不同，当且仅当选用的水晶或武器不同（可以在同一组）

由于战事紧迫，你需要迅速回答问题才能让Steve作出下一轮攻击的决策

因此，部分测试点强制在线

为了避免答案过大，答案对998244353998244353取模

输入格式

由于输入输出规模较大，使用下面的模板完成数据生成，具体格式请看模板和样例

评测时，所有测试点都只会输入5个数，输出1个数，因此你不需要输入输出优化

为便于调试，该模板可以手动指定数据，并输出每一个询问的答案，只需要输入的k=0k=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=0k=0，则会分别输出每一问的答案

否则，只会输出一个整数用于检查结果是否正确

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


18
2
6
4
2
18
16
0
12
12


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


11
2
5
3
2
11
9
0
6
6


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


11
0
6
5
6
5
0
6


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


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


3 2 233 5 10


15618218285282996994

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


988687952
712318441
204869162
71500349
703342331
285345621
783818790
712318441
712318441
276369511
703342331

提示

样例1解释：

当选择第二组武器时，一定能进行一次有效攻击

当选择第一组武器时，只有选择第一组水晶才能进行一次有效攻击

因而，不难求出每一问的答案

建议根据样例进一步理解题意

样例5与样例6一致

数据范围：

对于所有数据，满足1≤x,y,z,u≤n1\le x,y,z,u \le n，1≤ai,bi≤1091\le a_i,b_i\le 10^9，1≤nai,nbi≤9982443521\le na_i,nb_i\le 998244352

如未特别说明，k=3k=3，即：由模板生成数据，强制在线

如果k=2k=2，那么这组数据仍由生成器生成，但不强制在线，也就是你可以在不回答询问的情况下得到下一个询问的真实值，随后按顺序回答即可

测试点 分值 n q 特殊性质
1 4 100 k=2k=2
2 14 3000
3 11 100000 ai,bi≤100a_i,b_i\le 100
4 10 15 4000000
5 12 100
6 14 5000
7 16 100000
8 19 2500000 4000000
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. Language
  6. Theme
  2. 京ICP备2021032661号-1 京网文[2021]4533-1080号
  3. 京公网安备 11011102002149号
  4. © 2021-2024 Hydro.ac
  6. Powered by Hydro v4.16.1