[p1311]选择客栈

这题刚开始没想到可以枚举第二个客栈,选择了枚举第一个客栈.

因为只有一次询问,所以每个客栈最低消费的绝对值是没有意义的,有意义的只有这个客栈的最低消费与p的相对大小.

那么可以用1代表最低消费小于等于p,0代表大于p,对这个数组进行一次前缀和,那么这个前缀和就是一个具有单调性的数组.

这样枚举第一个客栈之后,可以用二分在logn时间内寻找出第一家可以喝咖啡的客栈,这家客栈之后的所有与第一家客栈色调相同的客栈都可以作为第二家客栈.

可以预处理出每一家客栈之后每种色调的客栈有多少个.

小细节:

1. 因为选择喝咖啡的客栈可以作为第一家或第二家客栈,所以在二分的时候寻找的不是前缀和为第一家客栈的前缀和+1的客栈,而是第一家客栈之前一家客栈的前缀和+1的客栈.即寻找的不是s[i]+1,而是s[i-1]+1.
2. 还是因为选择喝咖啡的客栈可以作为第一家或第二家客栈,预处理每一家客栈之后的每种色调的客栈数量时要包括这家客栈.但是这样会导致计算两人住在同一家客栈的方案,所以在枚举第一家客栈时,计算出可以去哪喝咖啡后,如果可以喝咖啡的客栈与第一家客栈相同,方案数应-1.

放一下我巨丑的代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define MAXN 200005
#define osu(a,b,i) for(int i = a;i <= b;i++)
#define nso(a,b,i) for(int i = a;i >= b;i--)
#define lovelive long long int
using namespace std;
int r[MAXN][55];
int sgn[MAXN];
int a[MAXN],s[MAXN];
int c[MAXN];
int N,K,P;
int ts[MAXN];
int init()
{
    //sgn
    osu(1,N,i)
    {
        if(a[i] <= P)sgn[i] = 1;
        else sgn[i] = 0;
    }
    //r
    memset(ts,0,sizeof ts);
    nso(N,1,i)
    {
        ts[c[i]]++;
        osu(0,K-1,j)
        {
            r[i][j] = ts[j];
        }
    }
    //s
    osu(1,N,i)
    {
        s[i] = s[i-1]+sgn[i];
    }
}
inline void read(int &ss)
{
    ss=0;char ch=getchar();while(ch>'9'||ch<'0')ch=getchar();
    while(ch>='0'&&ch<='9')ss*=10,ss+=ch-'0',ch=getchar();return;
}
int main()
{
    read(N);read(K);read(P);
    osu(1,N,i)
    {
        read(c[i]);read(a[i]);
    }
    init();
    lovelive ans = 0;
    osu(1,N,i)
    {
        int el=i,er=N;
        while(el < er)
        {
            int mid = ((el+er)>>1);
            if(s[mid] >= s[i-1] + 1)
            {
                er = mid;
            }else{
                el = mid +1;
            }
        }
        lovelive tans = 0;
        if(s[el] < s[i-1]+1)el = er;
        if(s[el] < s[i-1]+1)continue;
        tans += r[el][c[i]];
        if(el == i)tans--;
        ans += tans;
    }
    cout << ans << endl;
}