首页 > > 程序设计 > C/C++ >

HDU6301 Distinct Values （多校第一场1004）（…

2018-09-10 00:59:16来源：博客园阅读 ()

Distinct Values

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4869 Accepted Submission(s): 1659

Problem Description

Chiaki has an array of

Input

There are multiple test cases. The first line of input contains an integer

Output

For each test case, output

Sample Input

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

Sample Output

1 2 1 2 1 2 1 2 3 1 1

给出q个[l,r] 要求[l,r]范围内数字不重复，求字典序最小的满足q个要求的序列。

首先预处理出来覆盖每一个点的最左端点pre[i] ，用p从1开始和 pre[i]比较，(因为当前区间是[pre[i], i], 上个区间是 [p, i-1] ) 如果 p < pre[i] , 就把[p, pre[i]-1] 的数都释放了（插入set还能用）如果 p > pre[i], 直接取set.begin().

 1 // D
 2 #include <bits/stdc++.h>
 3 using namespace std;
 4 #define rep(i,a,n) for (int i=a;i<n;i++)
 5 #define per(i,a,n) for (int i=n-1;i>=a;i--)
 6 #define pb push_back
 7 #define mp make_pair
 8 #define all(x) (x).begin(),(x).end()
 9 #define fi first
10 #define se second
11 #define SZ(x) ((int)(x).size())
12 typedef vector<int> VI;
13 typedef long long ll;
14 typedef pair<int,int> PII;
15 const ll mod=1000000007;
16 ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
17 ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
18 // head
19 
20 const int N=101000;
21 int _,n,m,pre[N],l,r,ret[N];//pre维护覆盖i的最左端点 
22 int main() {
23     for (scanf("%d",&_);_;_--) {
24         scanf("%d%d",&n,&m);
25         rep(i,1,n+1) pre[i]=i;
26         rep(i,0,m) {
27             scanf("%d%d",&l,&r);
28             pre[r]=min(pre[r],l);
29         per(i,1,n) pre[i]=min(pre[i],pre[i+1]);//pre[i]是pre[i]和pre[i+1]的最小值
30         int pl=1;//从1开始 和覆盖每个点的最左端点pre[i]比较
31         set<int> val;
32         rep(i,1,n+1) val.insert(i);//维护最小可用的数
33         rep(i,1,n+1) {
34             //上个 [pl, i-1]
35 
36             //当前 [pre[i], i]
37             while (pl<pre[i]) {//小于pre[i]的点的值  插入set
38                 val.insert(ret[pl]);
39                 pl++;
40             }
41             ret[i]=*val.begin();//不小于直接取最小的数放进去
42             val.erase(ret[i]);//删除刚放入的数
43         }
44         rep(i,1,n+1) printf("%d%c",ret[i]," \n"[i==n]);
45     }
46 }