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

## 求解，线段树这样写为何会WA？

Posted by phoenix_hjp at 2014-07-27 15:07:20 on Problem 3067
```#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<map>
#include<vector>
#include<queue>
using namespace std;
int n,m,k;
struct node
{
int a,b;
}a[1005*1005];
struct tree
{
int l,r,sum;
}tree[1005<<2];
bool cmp(const node &a,const node &b)
{
if(a.a==b.a)
return a.b<b.b;
return a.a<b.a;
}
void build(int l,int r,int now)
{
tree[now].l=l;
tree[now].r=r;
tree[now].sum=0;
if(l==r)
return ;
int mid=(l+r)>>1;
build(l,mid,now<<1);
build(mid+1,r,now<<1|1);
}
void update(int t,int now)
{
if(tree[now].l==tree[now].r)
{
tree[now].sum++;
return ;
}
int mid=(tree[now].l+tree[now].r)>>1;
if(t<=mid)
{
update(t,now<<1);
tree[now].sum=(tree[now<<1].sum);
}
else
{
update(t,now<<1|1);
tree[now].sum=(tree[now<<1].sum+tree[now<<1|1].sum);
}
}
int main()
{
int t,cases=0;
cin>>t;
while(t--)
{
cin>>n>>m>>k;
for(int i=0;i<k;i++)
{
int t1,t2;
scanf("%d%d",&t1,&t2);
a[i].a=t1;
a[i].b=t2;
}
sort(a,a+k,cmp);
build(1,m,1);
long long ans=0;
for(int i=0;i<k;i++)
{
update(a[i].b,1);
ans+=(i+1-tree[1].sum);
}
++cases;
cout<<"Test case "<<cases<<": "<<ans<<endl;
}
return 0;
}```

Followed by: