题意：
There is a array contain N(1<N<=100000) numbers. Now give you M(1<M<10000) query.
Every query will be:
1 x : ask longest substring which every number no less than x
2 y x : change the A[y] to x. there are at most change 10 times.
For each ask can you tell me the length of longest substring.
思路：
简单题，因为修改的次数很少。
对于确定的n个数字，可以先把n个数字从小到大排序，然后从大到小依次进行线段块的合并（如果一个点左右的线段块都已经访问过了，说明大小满足覆盖要求），这很适合并查集的特点，所以可以用并查集加个权值，来记录每一块的线段长度。
然后每一次修改之后，就重新进行上面过程。然后之后的每一个查询，都是二分查表即可。（这个地方我想是可以有O(1)的处理方式的）
code：
#include<cstdio>#include<iostream>#include<sstream>#include<cstring>#include<algorithm>#include<vector>#include<string>#include<queue>#include<map>#include<set>#include<cmath>#include<cctype>#include<cstdlib>using namespace std;#define INF 0x3f3f3f3f#define PI acos(-1.0)#define mem(a, b) memset(a, b, sizeof(a))#define mod 1000000007typedef pair<int,int> pii;typedef long long LL;//——————————const int maxn = 100005;const int maxm = 10005;int n,m;int x[maxm], a[maxn];struct node{int num, id, ans;bool operator < (const node nt) const{return num < nt.num;}}b[maxn];int p[maxn], len[maxn];int find(int x){if(x == p[x]) return p[x];else return p[x] = find(p[x]);}void union_(int u, int v){int pu = find(u);int pv = find(v);if(pu != pv){p[pu] = pv;len[pv] += len[pu];}}void deal(){for(int i = 1; i <= n; i++){b[i].num = a[i];b[i].id = i;}sort(b+1, b+1+n);int max_ = 0;memset(len, 0, sizeof(len));for(int i = 1; i <= n; i++) p[i] = i;for(int i = n; i >= 1; i–){int id = b[i].id;len[id] = 1;if(len[id-1]) union_(id-1, id);if(len[id+1]) union_(id+1, id);if(max_ < len[find(id)]) max_ = len[find(id)];b[i].ans = max_;}// for(int i = 1; i <= n; i++){//printf("x = %d len = %d\n",b[i].num, b[i].ans);// }}int get_ans(int x){node tmp;tmp.num = x;int id = lower_bound(b+1, b+1+n, tmp) – b;// printf("x = %d id = %d\n",x,id);return b[id].ans;}void solve(){int op, a1, a2;deal();for(int i = 1; i <= m; i++){scanf("%d",&op);if(op == 2){scanf("%d%d",&a1,&a2);a[a1] = a2;deal();}if(op == 1){scanf("%d",&a1);if(a1 > b[n].num){printf("0\n");continue;}int ans = get_ans(a1);printf("%d\n",ans);}}}int main(){while(scanf("%d%d",&n,&m) != EOF){for(int i = 1; i <= n; i++){scanf("%d",&a[i]);}solve();}return 0;}
，他们的快乐像贪玩的小孩，游荡到天光却还不肯回来。
