树状数组的玄学的问题
查看原帖
树状数组的玄学的问题
55828
Charisk_FOD楼主2021/4/4 13:33

为啥加一个等于号的区别这么大?!
这个是我的代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<queue>
#include<stack>
#define _ 0
#define N 1000005

using namespace std;
int p,n,q,a[N*2],tr[N*2],ans[N*2];
struct qwe{
	int l,r;
	int id;
}qs[N*2];
int v[N*2];

long long read(){
	long long x=0,h=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')h=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+(long long)(ch-'0');ch=getchar();}
	return x*h;
}

inline int lowbit(int x){
	return x&(-x);
}
inline bool cmp(qwe a,qwe b){
	if(a.r==b.r) return a.l<b.l;
	return a.r<b.r;
}
inline void add(int x,int e){
	for( ;x<=n;x+=lowbit(x))tr[x]+=e;
	return ;
}
inline int query(int x){
	int sum=0;
	for( ;x>0;x-=lowbit(x))sum+=tr[x];
	return sum;
}

int main(){
	n=read();
	for(register int i=1;i<=n;i++)a[i]=read();
	q=read();
	for(register int i=1;i<=q;i++){
		qs[i].l=read();qs[i].r=read();
		qs[i].id=i;
	}
	sort(qs+1,qs+q+1,cmp);
	p=1;
	for(register int i=1;i<=q;i++){
		for( ;p<=qs[i].r;p++){
			if(v[a[p]])add(v[a[p]],-1);
			add(p,1);
			v[a[p]]=p;
		}
		ans[qs[i].id]=query(qs[i].r)-query(qs[i].l-1);
	}
	for(register int i=1;i<=q;i++)printf("%d\n",ans[i]);
	return 0;
} 

这个是AC代码。

但是如果把

inline bool cmp(qwe a,qwe b){
	return a.r<b.r;
}

改成

inline bool cmp(qwe a,qwe b){
	return a.r<=b.r;
}

#12 会WA
#13会TLE

Unaccept记录:记录
AC记录:记录

不知道有没有dalao解决一下这个问题

难道r相等交换的时间很久?

不会有所有询问的r都相等的bt情况吧

就算都相等,每次都交换,那nlogn也应该能过啊

一个WA一个TLE就离谱的要命qwq

2021/4/4 13:33
加载中...