| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
WA已经不错了。好好查代码吧。In Reply To:求解,线段树这样写为何会WA? Posted by:phoenix_hjp at 2014-07-27 15:07:20 > #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: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator