题目描述

Tobo 养了 n 只猪猪，猪猪们的编号为 1∼n。我们规定两种操作：
1.​对于给定的 l,r，表示 Tobo 要和编号为 l到 r 的猪猪按顺序玩耍，但因为 Tobo 喜新厌旧，所以已经玩耍过的猪猪不会再一起玩，会直接跳过它。
2.​对于给定的 x ，表示编号为 x 的猪猪想知道自己是第几个和 Tobo 玩耍的，如果没有玩耍过则输出 0 。

你一共需要处理 q次操作。

样例

10 10
1 7 9
2 4
2 10
1 1 9
2 1
1 2 7
2 2
1 6 10
2 8
1 2 2

0
0
4
5
2

很妙的一个优化就是，首次访问的时候，记录下每一个区间的右端点r，如果下次还访问到，直接跳过以前访问过的那段区间即可。

(暴力枚举+小优化) Code

#include<iostream>
#include<cstdio>
using namespace std;

const int N = 100010;
int ord[N],n,q,op,l,r,x;
int b[N];

int main()
{
    scanf("%d%d",&n,&q);
    int idx = 1;
    while(q--)
    {
        scanf("%d",&op);
        if(op==1)
        {
            scanf("%d%d",&l,&r);
            for(int i = l; i <= r; i ++)
            {
                if(ord[i] == 0)
                {
                    ord[i] = idx++;
                    b[i] = r;
                }
                else
                    i = b[i];
            }
        }
        else if(op == 2)
        {
            scanf("%d",&x);
            printf("%d\n",ord[x]);
        }
    }
    return 0;
}