POJ 3067 Japan

比眉伴天荒 2022-08-07 05:42 26阅读 0赞

#include <stdio.h>
    #include <algorithm>
    #include <cstring>
    #include <queue>
    
    using namespace std;
    
    
    struct node
    {
        int l, r;
    }a[1000*1001];
    
    bool cmp(const node &a, const node &b)
    {
        if(a.l == b.l)
            return a.r < b.r;
        return a.l < b.l;
    }
    
    struct fwtree
    {
        int n;
        int C[3000];
    
        void clear(int kk){ memset(C, 0, sizeof(C)); n=kk;}
    
        int lowbit(int x)
        {
            return x&(-x);
        }
    
        void add(int x)
        {
            while(x<=n){
                C[x]++;
                x += lowbit(x);
            }
        }
        __int64 sum(int x)
        {
            __int64 ret = 0;
            while(x>0){
                ret += C[x];
                x -= lowbit(x);
            }
            return ret;
        }
    };
    
    fwtree f;
    int main()
    {
        int t, m, n, cas, flag = 0;
        __int64 ans;
    
        scanf("%d", &t);
        while(t--){
            scanf("%d%d%d", &n, &m, &cas);
            for(int i=1; i<=cas; i++){
                scanf("%d%d", &a[i].l, &a[i].r);
            }
            sort(a+1, a+cas+1, cmp);
            f.clear(m);
            ans = 0;
    
            for(int i=cas; i>=1; i--){
                    ans += f.sum( a[i].r-1 );//自身不能加上，另种写法（从0开始）是 i-f.sum(a[i].r); 已经去掉了自身。
                f.add( a[i].r );
            }
         printf("Test case %d: %I64d\n", ++flag, ans);
        }
    
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，26人围观）

还没有评论，来说两句吧...

相关阅读

相关 POJ 3067 Japan （树状数组求逆序数---经典）

Japan <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</td> <t

青旅半醒/ 2024年02月17日 21:28/ 0 赞/ 26 阅读

相关 poj 1064 java_poj1064

Cable master Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 15127 Accept

r囧r小猫/ 2022年11月05日 03:30/ 0 赞/ 214 阅读

相关【POJ】：POJ 3984

题目链接：[http://poj.org/problem?id=3984][http_poj.org_problem_id_3984] 题目解析：这题算是搜索里面的简单题了吧

Myth丶恋晨/ 2022年08月23日 04:50/ 0 赞/ 232 阅读

相关 POJ 3067 Japan

include <stdio.h> include <algorithm> include <cstring> include <queue>

比眉伴天荒/ 2022年08月07日 05:42/ 0 赞/ 27 阅读

相关 POJ Tautology

Tautology <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</t

た入场券/ 2022年07月10日 04:16/ 0 赞/ 189 阅读

相关 POJ 3067-Japan（树状数组-逆序数）

Japan <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</td>

朴灿烈づ我的快乐病毒、/ 2022年06月16日 03:58/ 0 赞/ 207 阅读

相关 poj1321+poj2251

poj1321代码实现（dfs）： include <iostream> include <string.h> using namespace std

心已赠人/ 2022年05月30日 04:08/ 0 赞/ 213 阅读

相关 GCJ Japan 2011 决赛 B 题解《挑战程序设计竞赛》

[为什么80%的码农都做不了架构师？>>> ][80_] ![hot3.png][] ![GCJ Japan 2011 决赛 B 题解《挑战程序设计竞赛》][GCJ Jap

本是古典何须时尚/ 2022年01月15日 10:39/ 0 赞/ 171 阅读

相关 poj1007

1．链接地址 [https://vjudge.net/problem/POJ-1007][https_vjudge.net_problem_POJ-1007] 2．问题描述

深藏阁楼爱情的钟/ 2021年11月23日 15:38/ 0 赞/ 244 阅读

相关 poj 1009

参考自大神思路：[POJ 1009][] 首先，暴力必挂，这是题目的善意提醒。于是，一直在想不暴力的各种判断计算方法，关于各种跳跃移动，后来都无奈想用STL。原谅我的

刺骨的言语ヽ痛彻心扉/ 2021年11月02日 00:46/ 0 赞/ 251 阅读