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

Re:树状数组(先排序,按第一个元素升序,当第一个元素相同时,按第二个元素升序排序,在往上统计,往下维护),注意结果要用long long存

Posted by 0700302510 at 2017-08-06 16:37:13 on Problem 3067
In Reply To:树状数组(先排序,按第一个元素升序,当第一个元素相同时,按第二个元素升序排序,在往上统计,往下维护),注意结构要用long long存 Posted by:0700302510 at 2017-08-06 16:36:11
> #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:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator