Title Link https://www.luogu.org/problem/show?pid=1311#sub
Title Description

There are n distinctive Inns along the Lijiang River. The inns are numbered from 1 to N in order of their location. Each inn is decorated according to a certain color (a total of k, expressed in integer 0 - K - 1), and each inn has a coffee shop, each of which has its own minimum consumption.

Two tourists went to Lijiang together. They liked the same color and wanted to try two different hotels. So they decided to live in two Hotels with the same color. In the evening, they plan to choose a coffee shop for coffee, requiring that the coffee shop be located between the two hostels (including the one they live in) and that the minimum consumption of the coffee shop should not exceed p.

They want to know how many options there are to choose accommodation, so that they can find a coffee shop with a minimum consumption of no more than p yuan in the evening.

Input and output format

Input format:
Enter the file hotel.in, a total of n+1 lines.

The first row contains three integers n, k, p, separated by a space between each two integers, representing the number of inns, the number of tones and the maximum acceptable minimum consumption.

The next n lines, the two integers in line i+1, are separated by a space to indicate the decorative tone of inn i and the minimum consumption of the coffee shop in inn i.

Output format:
The output file is called hotel.out.

The output is a single line, an integer, representing the total number of alternative accommodation options.

Input and Output Samples

Input sample #1:
5 2 3
0 5
1 3
0 2
1 4
1 5
Output sample #1:
3
Explain

[Sample description of input and output]

Two people want to live in hotels of the same color. All the optional accommodation schemes include: staying in hotels (1), (2) and (4), (2) and (4). However, if you choose to stay in hotels 4 and 5, the minimum consumption of coffee shops between hotels 4 and 5 is 4, while the minimum consumption that two people can afford is 3 yuan, so they do not meet the requirements. So only the first three options are available.

[Data Scope]

For 30% of the data, n < 100;

For 50% of the data, n is less than 1,000;

For 100% data, there are 2 < n < 200,000, 0 < K < 50, 0 < p < 100.

This problem is solving the simulation of O(nk)...

But in fact, it can be used O(nlog(n)2) card, card time stimulation ah 2333

Enumeration of each starting point l, dichotomy to find the right endpoint r, so that the minimum value of the interval of l~r is less than k, then l contributes to the answer to the number of all points with the same color from R to n and l (all points with the same color on the right side of R and l can form a set of solutions with l)

The minimum interval and the number of points can be maintained by line segment trees, and the number of points can be counted by tree arrays.

Except for luogu, oj can pass basically. Luogu stabilizes T3 points (garbage assessor)

The code is as follows:

#include<cstdio>
using namespace std;
int n,m,k,ans,t=1,x,y;
int s[52][200050];
int read(){
    char c=getchar();
    int x=0;
    while(!(c>='0' && c<='9')) c=getchar();
    while(c>='0' && c<='9'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    return x;
}
inline int min(int a,int b){return a<b?a:b;}
struct Data{
    int k,x;
    inline void scan(){x=read();k=read();}
}a[200050];
inline void add(int x,int p,int v){
    for(;p<=n;p=p+(p&-p))
        s[x][p]+=v;
}
inline int sum(int x,int p){
    int tmp=0;
    for(;p;p=p-(p&-p))
        tmp=tmp+s[x][p];
    return tmp;
}
struct Node{
    int l,r,minn;
    Node *ls,*rs;
}q[1200050];
void maketree(int l,int r,Node *k){
    k->l=l;k->r=r;
    if(l==r){
        k->minn=a[l].k;
        return;
    }
    int mid=(l+r)>>1;
    k->ls=&q[++t];
    k->rs=&q[++t];
    maketree(l,mid,k->ls);maketree(mid+1,r,k->rs);
    k->minn=min(k->ls->minn,k->rs->minn);
}
int Query_min(int x,int y,Node *k){
    if(k->l>=x && k->r<=y) return k->minn;
    int mid=(k->l+k->r)>>1;
    if(x>mid) return Query_min(x,y,k->rs);
    if(y<=mid) return Query_min(x,y,k->ls);
    return min(Query_min(x,y,k->ls),Query_min(x,y,k->rs));
}
inline bool check(int l,int r){
    int t=Query_min(l,r,&q[1]);
    return t<=k?true:false;
}
int main(){
    n=read();m=read();k=read();
    for(int i=1;i<=n;i++){
        a[i].scan();
        add(a[i].x,i,1);
    }
    maketree(1,n,&q[1]);
    for(int i=n-1;i>=1;i--){
        int l=i+1,r=n,tmp=0;
        while(l<=r){
            int mid=(l+r)>>1;
            if(check(i,mid)) {tmp=mid;r=mid-1;}
            else l=mid+1;
        }
        if(!tmp) continue;
        ans=ans+sum(a[i].x,n)-sum(a[i].x,tmp-1);
    }
    printf("%d",ans);
return 0;
}

Evaluation record of codevs

luogu's evaluation records

Evaluation record of a small oj