就这份代码,将 N 设为 1e5+5 80分,剩下的RE。
改为 2e5+5 60分,剩下的TLE。
怎么奇怪的TLE了,不会和数组大小有关系吧。
#include <bits/stdc++.h>
#define mid ((l+r)>>1)
using namespace std;
int n, k, kkk;
bool flag;
const int N = 2e5 + 5;
struct node {
int a, b, c, ans, cnt;
bool operator<(const node& y) const {
if (!flag) {
if (a == y.a) {
if (b == y.b)return c < y.c;
else return b < y.b;
} else return a < y.a;
} else {
if (b == y.b) {
return c < y.c;
} else return b < y.b;
}
}
} s1[N], s2[N];
int top,m;
namespace BIT{
int t[N];
inline int lowbit(int x){
return x&(-x);
}
int query(int p){
int ret=0;
while(p){
ret+=t[p];
p-=lowbit(p);
}
return ret;
}
void update(int p,int v){
while(p<=kkk){
t[p]+=v;
p+=lowbit(p);
}
}
inline void clear(){
memset(t,0,sizeof(t));
}
}
void cdq(int l,int r){
if(l==r){
return;
}
cdq(l,mid);
cdq(mid+1,r);
sort(s2+l,s2+mid+1);
sort(s2+mid+1,s2+r+1);
int j=l;
for(int i=mid+1;i<=r;i++){
while(s2[i].b>=s2[j].b&&j<=mid){
BIT::update(s2[j].c,s2[j].cnt);
j++;
}
s2[i].ans+=BIT::query((s2[i].c));
}
BIT::clear();
}
int ans[N];
int main() {
cin >> n >> k;
kkk = k;
for (int i = 1, a, b, c; i <= n; i++) {
cin >> a >> b >> c;
s1[i].a = a;
s1[i].b = b;
s1[i].c = c;
}
sort(s1 + 1, s1 + n + 1);
for(int i = 1; i <= n; ++i) {
top++;
if (s1[i].a != s1[i + 1].a || s1[i].b != s1[i + 1].b || s1[i].c != s1[i + 1].c) {
m++;
s2[m].a = s1[i].a;
s2[m].b = s1[i].b;
s2[m].c = s1[i].c;
s2[m].cnt = top;
top = 0;
}
}
flag=1;
cdq(1,m);
for(int i=1;i<=m;i++){
ans[s2[i].ans+s2[i].cnt-1]+=s2[i].cnt;
}
for(int i=0;i<n;i++){
cout<<ans[i]<<'\n';
}
return 0;
}