题意:
给你一个由n个整数a1, a2, …, an组成的数组。最初ax=1,所有其他元素都等于0。
你必须进行m次操作。在第i次操作中,你选择两个指数c和d,使li≤c,d≤ri,并交换ac和ad。
计算指数k的数量,以便有可能选择操作,使ak=1。
大概就是说通过m次操作,能把哪几个位置换成1,可以看成ax是被染色的,只要在区间的块都能被染色,求最大的被染色的块。
思路:
先找到第一个包含x的区间,这个区间里的所有数都可以被染色,感觉可以当区间合并做
一开始我的区间只有个一点,m的最大范围只有100个,所以100个区间合并,求在x的区间长度,但是合并有原则得按照顺序合并,当前遍历到的区间不能和之后出现的区间合并,只能和之前的合并,所以只需要合并x和出现过x的区间即可
复杂度大概是O(m^2*t)大概1e6
#include<bits/stdc++.h> using namespace std; const int maxn=105; struct node { int l,r; }mo[maxn]; int main() { int n,i,j,t,m,x; cin>>t; while(t--) { int l1,r1; cin>>n>>x>>m; int cnt=0; mo[cnt].r=x; mo[cnt++].l=x; for(i=0;i<m;i++) { cin>>l1>>r1; int flag=0; for(j=0;j<1;j++) { if((l1>=mo[j].l&&l1<=mo[j].r)||(r1<=mo[j].r&&r1>=mo[j].l)||(l1<=mo[j].l&&r1>=mo[j].r)) { mo[j].l=min(mo[j].l,l1); mo[j].r=max(mo[j].r,r1); } } } for(i=0;i<cnt;i++) { if(x>=mo[i].l&&x<=mo[i].r) { cout<<mo[i].r-mo[i].l+1<<endl; break; } } } return 0; }