小猪头由于太蠢了,所以不知道怎么计算树状数组套动态开点线段树中线段树所需要的空间,所以想请教一下各位神仙,套着的这个线段树空间要开多大哇。 100pts 树套树code:
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 2e5 + 17;
struct node
{
int a,b,c,cnt;
}d[MAXN],D[MAXN];
int n,K,cnt;
int lc[50 * MAXN],rc[50 * MAXN],sum[50 * MAXN],ans[MAXN];
void change(int k,int l,int r,int pos,int val)
{
if(l == pos && pos == r)
{
sum[k] += val;
return;
}
int mid = (l + r) >> 1;
if(pos <= mid)
{
if(!lc[k])lc[k] = ++cnt;
change(lc[k],l,mid,pos,val);
}
else {
if(!rc[k])rc[k] = ++cnt;
change(rc[k],mid + 1,r,pos,val);
}
sum[k] = sum[lc[k]] + sum[rc[k]];
}
int check(int k,int l,int r,int x,int y)
{
if(l >= x && r <= y)return sum[k];
int mid = (l + r) >> 1;
int ans = 0;
if(x <= mid)
if(lc[k])ans += check(lc[k],l,mid,x,y);
if(mid < y)
if(rc[k])ans += check(rc[k],mid + 1,r,x,y);
return ans;
}
struct BIT
{
int rt[MAXN];
int lowbit(int x){
return x & (-x);
}
void insert(int x,int y,int val){
for(;x <= K;x += lowbit(x))
{
if(!rt[x])rt[x] = ++cnt;
change(rt[x],1,K,y,val);
}
}
int query(int x,int y){
int ans = 0;
for(;x;x -= lowbit(x))
{
if(rt[x])ans += check(rt[x],1,K,1,y);
}
return ans;
}
}tr;
bool cmp1(node A,node B)
{
if(A.a == B.a)
{
if(A.b == B.b)return A.c < B.c;
return A.b < B.b;
}
return A.a < B.a;
}
int main()
{
scanf("%d%d",&n,&K);
for(int i = 1;i <= n;i += 1)
scanf("%d%d%d",&d[i].a,&d[i].b,&d[i].c);
sort(d + 1,d + n + 1,cmp1);
int tot = 0;
int m = 0;
for(int i = 1;i <= n;i += 1)
{
tot++;
if(d[i].a != d[i + 1].a || d[i].b != d[i + 1].b || d[i].c != d[i + 1].c)
{
m++;
D[m].a = d[i].a;
D[m].b = d[i].b;
D[m].c = d[i].c;
D[m].cnt = tot;
tot = 0;
}
}
for(int i = 1;i <= m;i += 1)
{
ans[tr.query(D[i].b,D[i].c) + D[i].cnt - 1] += D[i].cnt;
tr.insert(D[i].b,D[i].c,D[i].cnt);
}
for(int i = 0;i < n;i += 1)
printf("%d\n",ans[i]);
return 0;
}