济南单位网站建设,四川省住房建设厅网站,西部数据网站管理助手,电子购物网站建设正题
题目链接:https://jzoj.net/senior/#main/show/3236 题目大意
一个序列两个操作 1XY:1\ X\ Y:1 X Y:交换XXX和YYY两个数2AB:2\ A\ B:2 A B:询问A∼BA\sim BA∼B这些数再序列中是否是连续的一段区间(不一定按顺序) 解题思路
先不考虑交换#xff0c;对于询问我们发现它…正题
题目链接:https://jzoj.net/senior/#main/show/3236 题目大意
一个序列两个操作
1XY:1\ X\ Y:1 X Y:交换XXX和YYY两个数2AB:2\ A\ B:2 A B:询问A∼BA\sim BA∼B这些数再序列中是否是连续的一段区间(不一定按顺序) 解题思路
先不考虑交换对于询问我们发现它询问的区间不固定所以很难用线段树来做。所以我们可以用域值iii维护iii再目前序列的哪个位置。然后维护区间最大值和最小值然后若询问B−AB-AB−A等于A∼BA\sim BA∼B这个区间的maxn−minnmaxn-minnmaxn−minn那么这些是一个连续区间。
然后交换我们定义segiseg_isegi表示在iii这个位置的数然后就直接根据这个修改线段树然后交换。 codecodecode
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N201000;
int n,m,id[N],seg[N],rea,rei;
struct Tree_node{int l,r,mins,maxs;
};
struct Seg_Tree{Tree_node t[N2];void Updata(int x,int ls,int rs){t[x].minsmin(t[ls].mins,t[rs].mins);t[x].maxsmax(t[ls].maxs,t[rs].maxs);return;}void Build(int x,int l,int r){t[x].ll;t[x].rr;if(lr){t[x].minst[x].maxsid[l];return;}int mid(lr)/2;Build(x*2,l,mid);Build(x*21,mid1,r);Updata(x,x*2,x*21);}void Ask(int x,int l,int r){if(t[x].llt[x].rr){Updata(0,0,x);return;}if(rt[x*2].r) Ask(x*2,l,r);else if(lt[x*21].l) Ask(x*21,l,r);else Ask(x*2,l,t[x*2].r),Ask(x*21,t[x*21].l,r);}void Change(int x,int pos,int z){if(t[x].lt[x].r){t[x].minst[x].maxsz;return;}if(post[x*2].r) Change(x*2,pos,z);else Change(x*21,pos,z);Updata(x,x*2,x*21);}
}Tree;
void Query(int l,int r)
{Tree.t[0].minsn1;Tree.t[0].maxs0;Tree.Ask(1,l,r);reiTree.t[0].mins;reaTree.t[0].maxs;
}
void Swap(int x,int y)
{Query(x,x);int a1rei;Query(y,y);int a2rei;Tree.Change(1,x,a2);Tree.Change(1,y,a1);
}
int main()
{scanf(%d%d,n,m);for(int i1;in;i){int x;scanf(%d,x);id[x]i;seg[i]x;}Tree.Build(1,1,n);while(m--){int op,x,y;scanf(%d%d%d,op,x,y);if(op1){Swap(seg[x],seg[y]);swap(seg[x],seg[y]);}else{Query(x,y);if(rea-reiy-x) printf(YES\n);else printf(NO\n);}}
}
