蒟蒻对数据范围的疑问
查看原帖
蒟蒻对数据范围的疑问
983702
lrj3247楼主2024/8/13 21:13

一开始是这样的

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+15,MAXN=4e5+15;
inline int read(){
	int w=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while('0'<=ch&&ch<='9'){
		w=w*10+ch-'0';
		ch=getchar();
	}
	return w*f;
}
inline void write(long long x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
struct Node{
	int l,r,ls,rs;
	long long sum;
	/*Node(){
		ls=rs=l=r=0;
		sum=1;
	}*/
}tr[N<<2];
int t,Q,M,op,m,idx,cnt,rt;

void pushup(Node &fa,Node &ls,Node &rs){
	fa.sum=ls.sum*rs.sum%M;
}
void build(int &id,int l,int r,int k,int x){
	if(!id){
		id=++idx;
	}
	tr[id].l=l,tr[id].r=r;
	if(l==r){
		tr[id].sum=k;
		//cout<<"id:"<<id<<" l:"<<l<<" r:"<<r<<" sum:"<<tr[id].sum<<endl;
		return ;
	}
	int mid=l+r>>1;
	if(x<=mid) build(tr[id].ls,l,mid,k,x);
	else if(x>mid) build(tr[id].rs,mid+1,r,k,x);
	pushup(tr[id],tr[tr[id].ls],tr[tr[id].rs]);
	//cout<<"id:"<<id<<" l:"<<l<<" r:"<<r<<" sum:"<<tr[id].sum<<endl;
}
void modify(int id,int x){
	int l=tr[id].l,r=tr[id].r;
	if(l==r){
		tr[id].sum=1;
		return ;
	}
	int mid=l+r>>1;
	if(x<=mid) modify(tr[id].ls,x);
	else if(x>mid) modify(tr[id].rs,x);
	pushup(tr[id],tr[tr[id].ls],tr[tr[id].rs]);
}
signed main(){
	//freopen("num.in","r",stdin);
	//freopen("num1.out","w",stdout);
	t=read();
	while(t--){
		unordered_map <long long,long long> mp;
		for(int i = 0 ; i<=MAXN ; i++) tr[i]={0,0,0,0,1};
		cnt=0;
		Q=read(),M=read();
		for(int i = 1 ; i<=Q ; i++){
			op=read(),m=read();
			if(op==1){
				++cnt;
				mp[i]=cnt;
				build(rt,1,Q,m,cnt);
			}
			else{
				modify(1,mp[m]);
			}
			write(tr[1].sum);
			putchar('\n');
		}
	}
	return 0;
}
/*
1
9 552
1 10
1 4
1 7
2 2
1 6
1 9
2 5
2 2
2 3
*/

然后RE了8个点，将N和MAXN改大了之后 就AC了

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+15,MAXN=8e5+15;
inline int read(){
	int w=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while('0'<=ch&&ch<='9'){
		w=w*10+ch-'0';
		ch=getchar();
	}
	return w*f;
}
inline void write(long long x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
struct Node{
	int l,r,ls,rs;
	long long sum;
	/*Node(){
		ls=rs=l=r=0;
		sum=1;
	}*/
}tr[N<<2];
int t,Q,M,op,m,idx,cnt,rt;

void pushup(Node &fa,Node &ls,Node &rs){
	fa.sum=ls.sum*rs.sum%M;
}
void build(int &id,int l,int r,int k,int x){
	if(!id){
		id=++idx;
	}
	tr[id].l=l,tr[id].r=r;
	if(l==r){
		tr[id].sum=k;
		//cout<<"id:"<<id<<" l:"<<l<<" r:"<<r<<" sum:"<<tr[id].sum<<endl;
		return ;
	}
	int mid=l+r>>1;
	if(x<=mid) build(tr[id].ls,l,mid,k,x);
	else if(x>mid) build(tr[id].rs,mid+1,r,k,x);
	pushup(tr[id],tr[tr[id].ls],tr[tr[id].rs]);
	//cout<<"id:"<<id<<" l:"<<l<<" r:"<<r<<" sum:"<<tr[id].sum<<endl;
}
void modify(int id,int x){
	int l=tr[id].l,r=tr[id].r;
	if(l==r){
		tr[id].sum=1;
		return ;
	}
	int mid=l+r>>1;
	if(x<=mid) modify(tr[id].ls,x);
	else if(x>mid) modify(tr[id].rs,x);
	pushup(tr[id],tr[tr[id].ls],tr[tr[id].rs]);
}
signed main(){
	//freopen("num.in","r",stdin);
	//freopen("num1.out","w",stdout);
	t=read();
	while(t--){
		unordered_map <long long,long long> mp;
		for(int i = 0 ; i<=MAXN ; i++) tr[i]={0,0,0,0,1};
		cnt=0;
		Q=read(),M=read();
		for(int i = 1 ; i<=Q ; i++){
			op=read(),m=read();
			if(op==1){
				++cnt;
				mp[i]=cnt;
				build(rt,1,Q,m,cnt);
			}
			else{
				modify(1,mp[m]);
			}
			write(tr[1].sum);
			putchar('\n');
		}
	}
	return 0;
}
/*
1
9 552
1 10
1 4
1 7
2 2
1 6
1 9
2 5
2 2
2 3
*/

过了一段时间又觉得idx没有清0，所以RE。 于是每次将idx改成0。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+15,MAXN=4e5+15;
inline int read(){
	int w=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while('0'<=ch&&ch<='9'){
		w=w*10+ch-'0';
		ch=getchar();
	}
	return w*f;
}
inline void write(long long x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
struct Node{
	int l,r,ls,rs;
	long long sum;
	/*Node(){
		ls=rs=l=r=0;
		sum=1;
	}*/
}tr[N<<2];
int t,Q,M,op,m,idx,cnt,rt;

void pushup(Node &fa,Node &ls,Node &rs){
	fa.sum=ls.sum*rs.sum%M;
}
void build(int &id,int l,int r,int k,int x){
	if(!id){
		id=++idx;
	}
	tr[id].l=l,tr[id].r=r;
	if(l==r){
		tr[id].sum=k;
		//cout<<"id:"<<id<<" l:"<<l<<" r:"<<r<<" sum:"<<tr[id].sum<<endl;
		return ;
	}
	int mid=l+r>>1;
	if(x<=mid) build(tr[id].ls,l,mid,k,x);
	else if(x>mid) build(tr[id].rs,mid+1,r,k,x);
	pushup(tr[id],tr[tr[id].ls],tr[tr[id].rs]);
	//cout<<"id:"<<id<<" l:"<<l<<" r:"<<r<<" sum:"<<tr[id].sum<<endl;
}
void modify(int id,int x){
	int l=tr[id].l,r=tr[id].r;
	if(l==r){
		tr[id].sum=1;
		return ;
	}
	int mid=l+r>>1;
	if(x<=mid) modify(tr[id].ls,x);
	else if(x>mid) modify(tr[id].rs,x);
	pushup(tr[id],tr[tr[id].ls],tr[tr[id].rs]);
}
signed main(){
	//freopen("num.in","r",stdin);
	//freopen("num1.out","w",stdout);
	t=read();
	while(t--){
		unordered_map <long long,long long> mp;
		for(int i = 0 ; i<=MAXN ; i++) tr[i]={0,0,0,0,1};
		idx=0,cnt=0;
		Q=read(),M=read();
		for(int i = 1 ; i<=Q ; i++){
			op=read(),m=read();
			if(op==1){
				++cnt;
				mp[i]=cnt;
				build(rt,1,Q,m,cnt);
			}
			else{
				modify(1,mp[m]);
			}
			write(tr[1].sum);
			putchar('\n');
		}
	}
	return 0;
}
/*
1
9 552
1 10
1 4
1 7
2 2
1 6
1 9
2 5
2 2
2 3
*/

然后——就全部MLE了！！！ 求问为什么

2024/8/13 21:13