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

## 树状数组（先排序，按第一个元素升序，当第一个元素相同时，按第二个元素升序排序，在往上统计，往下维护），注意结构要用long long存

Posted by 0700302510 at 2017-08-06 16:36:11 on Problem 3067
```#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int inf=1000100;
struct node{
int st,ed;
}th[inf];
long long shu[inf];
int n,m,k;
int same[inf];
bool tmp(node a,node b)
{
if(a.st==b.st)
return a.ed<b.ed;
return a.st<b.st;
}
int lowbit(int i)
{
return i&(-1*i);
}
int sum(int i)
{
long long ans;
ans=0;
while(i<=inf){
ans+=shu[i];
i+=lowbit(i);
}
return ans;
}
void reset(int i)
{
while(i>0){
shu[i]+=1;
i-=lowbit(i);
}
}
int main()
{
int num;
int i,j;
scanf("%d",&num);
int N=0;
while(num--){
memset(same,0,sizeof(same));
memset(shu,0,sizeof(shu));
scanf("%d %d %d",&n,&m,&k);
for(i=0;i<k;i++){
scanf("%d %d",&th[i].st,&th[i].ed);
}
sort(th,th+k,tmp);
/* for(i=0;i<k;i++){
printf("%d %d\n",th[i].st,th[i].ed);
}*/
long long ans=0;
for(i=0;i<k;i++){
ans+=sum(th[i].ed+1);
same[th[i].ed]++;
reset(th[i].ed);
}
printf("Test case %d: %lld\n",++N,ans);
}
return 0;
}```

Followed by: