Problem Description

Chiaki has an array of

n positive integers. You are told some facts about the array: for every two elements ai and aj in the subarray al..r (l≤i<j≤r ), ai≠aj holds.

Chiaki would like to find a lexicographically minimal array which meets the facts.

 

 

Input

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

T , indicating the number of test cases. For each test case:

The first line contains two integers n and m (1≤n,m≤105 ) -- the length of the array and the number of facts. Each of the next m lines contains two integers li and ri (1≤li≤ri≤n ).

It is guaranteed that neither the sum of all n nor the sum of all m exceeds 106 .

 

 

Output

For each test case, output

n integers denoting the lexicographically minimal array. Integers should be separated by a single space, and no extra spaces are allowed at the end of lines.

 

 

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

 

这回的航电多校有多个签到题 好评 

 

  这题就用L,R 两个指针维护这个ans序列

　

while(L < qu[i].l) {

     st.insert(ans[L]);

     L++;

}

这些值可以重新插入

while(R < qu[i].r) {

if (R < qu[i].l-1) R++;

else {

       R++;

      ans[R] = *st.begin();

      st.erase(st.begin());

      }

}

这个其实类似于莫队的区间维护

1 #include 
      
        2 using namespace std; 3 const int maxn = 1e6 + 10; 4 int t, n, m, ans[maxn]; 5 struct node { 6     int l, r, flag; 7 } qu[maxn]; 8 int cmp(node a, node b) { 9     if (a.l == b.l) return a.r < b.r;10     return a.l < b.l;11 }12 int main() {13     scanf("%d", &t);14     while(t--) {15         scanf("%d%d", &n, &m);16         for (int i = 0 ; i < m ; i++) {17             scanf("%d%d", &qu[i].l, &qu[i].r);18             qu[i].flag = 0;19         }20         sort(qu, qu + m, cmp);21         set
       
        st;22         for (int i = 1 ; i <= n ; i++) {23             st.insert(i);24             ans[i] = 1;25         }26         for (int i = qu[0].l ; i <= qu[0].r ; i++) {27             ans[i] = *st.begin();28             st.erase(st.begin());29         }30         int L = qu[0].l, R = qu[0].r;31         for (int i = 1 ; i < m ; i++) {32             while(L < qu[i].l) {33                 st.insert(ans[L]);34                 L++;35             }36             while(R < qu[i].r) {37                 if (R < qu[i].l-1) R++;38                 else {39                     R++;40                     ans[R] = *st.begin();41                     st.erase(st.begin());42                 }43             }44         }45         for (int i = 1 ; i <= n ; i++) {46             if (i != n)  printf("%d ", ans[i]);47             else printf("%d\n", ans[i]);48         }49     }50     return 0;51 }