TLE30pts，不清楚为啥会TLE

常规
1

题面：
屏幕截图 2025-04-12 191330
屏幕截图 2025-04-12 191343
TLE30pts代码：

#include<bits/stdc++.h>
using namespace std;
//#define int long long
const int N=15000+5;
struct node{
	int x,y;
}a[N];
bool cmp(node xx,node yy){
    if(xx.x==yy.x)
        return xx.y<yy.y;
	return xx.x<yy.x;
}
int t[32005],d[N];
int lowbit(int x){
	return x&(-x);
}
void add(int x){
	for(int i=x;i<=32000;i+=lowbit(i))
	    t[i]++;
}
int query(int x){
	int ans=0;
	for(int i=x;i>0;i-=lowbit(i))
	    ans+=t[i];
	return ans;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	    cin>>a[i].x>>a[i].y;
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++){
        int kkk=query(a[i].y);
		d[kkk]++;
		add(a[i].y);
	}
	for(int i=0;i<n;i++)
	    cout<<d[i]<<'\n';
}

应该是add函数导致的TLE，但本蒟蒻不会优化，求大佬解答qwq

2

你可以把上限改成最大的 y 坐标。

3 
#include<bits/stdc++.h>
using namespace std;
//#define int long long
const int N=15000+5;
struct node{
	int x,y;
}a[N];
bool cmp(node xx,node yy){
    if(xx.x==yy.x)
        return xx.y<yy.y;
	return xx.x<yy.x;
}
int t[32005],d[N],Max;
int lowbit(int x){
	return x&(-x);
}
void add(int x){
	for(int i=x;i<=Max;i+=lowbit(i))
	    t[i]++;
}
int query(int x){
	int ans=0;
	for(int i=x;i>0;i-=lowbit(i))
	    ans+=t[i];
	return ans;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
	    cin>>a[i].x>>a[i].y;
        Max=max(Max,a[i].y);
    }
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++){
        int kkk=query(a[i].y);
		d[kkk]++;
		add(a[i].y);
	}
	for(int i=0;i<n;i++)
	    cout<<d[i]<<'\n';
}

还是TLE30pts

1 个赞
4

c，咋搞AC了？

5

寝室后人，小心0的情况，@我命由我不由天，关贴！