比赛地址

华东交通大学2019年ACM 双基 程序设计竞赛

H谁在说谎（HAOI2011原题：P2519 [HAOI2011]problem a）

题目描述

一次考试共有 \(n\) 个人参加，可能出现多个人成绩相同的情况。第 \(i\) 个人说：“有 \(a_i\) 个人成绩比我高，\(b_i\) 个人成绩比我低。”

请求出最少有几个人没有说真话。

输入格式

输入的第一行是一个整数，代表参加考试的人数 \(n\)。

第 \(2\) 到第 \((n + 1)\) 行，每行两个用空格隔开的整数，第 \((i + 1)\) 行的两个整数分别代表比第 \(i\) 个人成绩高的人数 \(a_i\) 和比第 \(i\) 个人成绩低的人数 \(b_i\)。

输出格式

输出一行一个整数，代表最少有几个人没有说真话。

输入

3
2 0
0 2
2 2

输出

1

说明/提示

对于 \(100\%\) 的数据，保证 \(1 \leq n \leq 10^5\)，\(0 \leq a_i, b_i \leq n\)。

解题思路

将题意转换：求说真话的最多人数
有 \(a\) 个人成绩比我高，\(b\) 个人成绩比我低说明：排名在 \(a+1\sim n-b\) 的同学的分数一样，设 \(l=a+1,r=n-b\)，如果 \(l\ge r\) 说明此人一定在说假话，不用管，把这些可能说真话的同学的区间提取出来，给每一个区间的初始权值设为 \(1\)，如果存在区间（用 \(([l,r]\) 表示）相同，则这些区间权值为相同区间数，表示说这个区间的同学分数相同的有这么多同学，但不应该超过 \(r-l+1\) 人，因为最多情况是正好说这话的同学排名正好处于该区间内，题目又可转化为在一堆区间中，找出一堆不相交且权值最大的区间。不妨先将右端点排序，使用dp：

• 状态表示：\(f[i]\) 表示前 \(i\) 个区间中不相交的区间的最大权值和
• 状态计算：\(f[i]=max(f[i-1],f[k]+b[i].v)\)，其中 \(k\) 为 \(1\sim i-1\) 中满足\(b[k].r 的最大的 \(k\)，正好可以二分找到这样的 \(k\)
• 时间复杂度：\(O(nlogn)\)

代码

#include
using namespace std;
const int N=1e5+5;
struct Range
{
    int l,r,v;
}a[N],b[N];
bool cmp1(Range &a,Range &b)
{
    if(a.l!=b.l)return a.l>1;
        if(b[mid].r

#include
using namespace std;
const int mod=666666;
int n,m;
void mul(int f[],int a[][2])
{
    int c[2];
    memset(c,0,sizeof c);
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            c[i]=(c[i]+1ll*f[j]*a[j][i])%mod;
    memcpy(f,c,sizeof f);
}
void mulself(int a[][2])
{
    int c[2][2];
    memset(c,0,sizeof c);
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            for(int k=0;k<2;k++)
                c[i][j]=(c[i][j]+1ll*a[i][k]*a[k][j])%mod;
    memcpy(a,c,sizeof c);
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        int f[2]={4,233},a[2][2]={{0,3},{1,4}};
        n--;
        for(;n;n>>=1)
        {
            if(n&1)mul(f,a);
            mulself(a);
        }
        printf("%d\n",m-f[0]);
    }
    return 0;
}