Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 解题思路以及个人写法：BIT or 线段树

Posted by 947186602 at 2020-09-15 10:26:15 on Problem 2352 and last updated at 2020-09-15 10:26:47
```/**

Sample Input
5
1 1
5 1
7 1
3 3
5 5
Sample Output
1
2
1
1
0

**/

//BIT 140ms
#include<cstdio>
#include<string.h>
using namespace std;
const int MAX_N = 15005,MAX_X = 32005;
int num[MAX_N],N;
int BIT[MAX_X << 1];

int sum(int n){
int res = 0;
while(n > 0){
res += BIT[n];
n -= (n&-n);
}
return res;
}

while(n <= MAX_X){
BIT[n] += v;
n += (n&-n);
}
}

int solve_bit(int x,int y){
int now = sum(x+1);
return now;
}

int main(){
while(~scanf("%d",&N)){
int x,y;
memset(num,0,sizeof(num));
memset(num,0,sizeof(BIT));
for(int i = 0;i < N;++i){
scanf("%d%d",&x,&y);
int sum = solve_bit(x,y);
num[sum]++;
}
for(int i = 0;i < N;++i){
printf("%d\n",num[i]);
}
}
return 0;
}

-----------------------------------------------------------------
//线段树 188ms
#include<cstdio>
#include<string.h>
using namespace std;
const int MAX_N = 15005,MAX_X = 32005;
int num[MAX_N],N;
int tree[MAX_X << 2];

void update(int node,int L,int R,int pos,int v){
if(L == R && L == pos){
tree[node] += v;
return;
}
int mid = L + R >> 1;
if(pos <= mid)
update(node << 1,L,mid,pos,v);
if(pos > mid)
update(node << 1 | 1,mid + 1,R,pos,v);
tree[node] = tree[node << 1] + tree[node << 1 | 1];
}

int query(int node,int L,int R,int l,int r){
if(l <= L && R <= r){
return tree[node];
}
int res = 0;
int mid = L + R >> 1;
if(l <= mid){
res += query(node << 1, L , mid,l,r);
}
if(r > mid){
res += query(node << 1 | 1,mid+1,R,l,r);
}
return res;
}

int main(){
while(~scanf("%d",&N)){
int x,y;
memset(tree,0,sizeof(tree));
for(int i = 0;i < N;++i){
scanf("%d%d",&x,&y);
int r = query(1,1,MAX_X,1,x+1);
num[r]++;
update(1,1,MAX_X,x+1,1);
}
for(int i = 0;i < N;++i){
printf("%d\n",num[i]);
}
}
return 0;
}
```

Followed by: