欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

POJ 6301 Distinct Values

程序员文章站 2022-06-17 19:48:16
...

POJ 6301 Distinct Values

题 意:给你一个大小为n的数组,给定m次询问,每次询问输入(l,r)表示l <= i < j <=r。
a[i]!= a[j]
数据范围:
1 <=m<=1e5
1 < n < 1e5 题面上说n可以等于1,其实n=1就没意义了

输入样例:

3
2 1
1 2
4 2
1 2
3 4
5 2
1 3
2 4

输出样例:

1 2
1 2 1 2
1 2 3 1 1

收 获:
思 路:注意三种情况,然后从左到右去贪心就好。
POJ 6301 Distinct Values

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#define N 1000005
#define rep(i,a,n) for(int i=a;i<n;i++)
#define per(i,a,n) for(int i=n-1;i>=a;i++)
using namespace std;
typedef long long ll;
const int maxn = 1e5+5;
struct node{
    int l,r;
}a[maxn];
int MAX[maxn];
int num[maxn];
bool mp[maxn];
vector<int> vec;
int n,m;
bool cmp(node p,node q){
    if(p.l < q.l) return true;
    else if(p.l == q.l && p.r > q.r)return true;
    else return false;
}
void init(){
    memset(MAX,0,sizeof(MAX));
    memset(num,0,sizeof(num));
    memset(mp,false,sizeof(mp));
}
int main() {
    int t;
    scanf("%d",&t);
    while(t--){
        init();
        vec.clear();
        scanf("%d %d",&n,&m);
        for(int i=0;i<m;i++){
            scanf("%d %d",&a[i].l,&a[i].r);
        }
        sort(a,a+m,cmp);
        MAX[0] = a[0].r;
        for(int i=1;i<m;i++){
            MAX[i] = max(MAX[i-1],a[i].r);
        }
        for(int i=1;i<a[0].l;i++){
            num[i] = 1;
            vec.push_back(1);
        }
        int number = 1;
        for(int i=a[0].l;i<=a[0].r;i++){
            num[i] = number;
            vec.push_back(number++);
        }
        for(int i=1;i < m;i++){
            number = 1;
            if(a[i].r <= MAX[i-1]) continue;
            if(a[i].l <= MAX[i-1] && a[i].r > MAX[i-1]){
                for(int j=a[i].l;j<=MAX[i-1];j++){
                    int ans = num[j];
                    mp[ans] = true;
                }
                for(int j=MAX[i-1]+1;j<=a[i].r;j++){
                    while(mp[number]){
                        number++;
                    }
                    num[j] = number;
                    vec.push_back(number++);
                }
                for(int j=a[i].l;j<=MAX[i-1];j++){
                    int ans = num[j];
                    mp[ans] = false;
                }
            }
            if(a[i].l >MAX[i-1]){
                for(int j=MAX[i-1]+1;j<a[i].l;j++){
                    vec.push_back(1);
                }
                for(int j=a[i].l;j<=a[i].r;j++){
                    num[j] = number;
                    vec.push_back(number++);
                }
            }
        }
        for(int i=MAX[m-1]+1;i<=n;i++){
            vec.push_back(1);
        }
        for(int i=0;i<vec.size();i++){
            printf("%d%c",vec[i],i==vec.size()-1?'\n':' ');
        }
    }
    return 0;
}
/*
3
6 2
1 2
3 6
*/