Detail of message

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

树状数组（先排序，按第一个元素升序，当第一个元素相同时，按第二个元素升序排序，在往上统计，往下维护），注意结构要用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:

Post your reply here:

User ID:
Password:
Title:

Content:

> #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;
> }

Home Page Go Back To top