网站权限设置,做微商网站制作,服饰类行业_如果要建设网站_说明其建站流程.,企业计划书怎么写Problem B 发布时间: 2017年7月1日 02:08 最后更新: 2017年7月1日 02:10 时间限制: 1000ms 内存限制: 64M 描述 给定一个长度为n的序列a1, a2, ..., an, 满足这个序列是一个1~n的排列 如果一个序列满足: 将序列排序后, 任意两个相邻的元素的差为1, 那么就称这个序列为 发布时间: 2017年7月1日 02:08 最后更新: 2017年7月1日 02:10 时间限制: 1000ms 内存限制: 64M 描述 给定一个长度为n的序列a1, a2, ..., an, 满足这个序列是一个1~n的排列 如果一个序列满足: 将序列排序后, 任意两个相邻的元素的差为1, 那么就称这个序列为胖虎序列 给出q个操作, 操作分为两种 对于形如1 x y的操作, 交换ax和ay, 满足1≤xy≤n 对于形如2 x y的操作, 判断区间[x,y]内的元素构成的序列是否为一个胖虎序列, 如果是, 输出YES, 否则输出NO, 满足1≤x≤y≤n 9×104≤n≤105, 9×104≤q≤105 输入 第一行两个整数n, q, 意义如上所述。 第二行n个整数, 表示序列a。 接下来q行, 每行第一个数为opt, 之后紧跟两个数, 意义如上所述。 输出 对于每个操作2, 输出答案, 一行一个。 样例输入1 复制 5 3
1 2 4 3 5
2 1 3
1 3 4
2 1 3 样例输出1 NO
YES 这是一道比较有意思的题题目给出一个1到n的排列然后两种操作
1交换任何两个数
2选取一段连续的区间并判断能否构成等差数列且 公差为1 判断等差序列的时候我们先找到这段序列的最小值以及最大值然后假设其为等差序列估计出区间和然后和维护的真实区间和进行比对如果相等就是等差序列否则的话就不是
我们用到的区间求最大值最小值以及区间和的数据结构都是线段树。
代码 #include iostream
#include cstdio
#include algorithm
using namespace std;
const int MAX 100007;
const int INF 1e9;
int st[MAX2][3];
int a[MAX];
int n,q;
int ops(int a,int b,int op){switch(op){case 0:return max(a,b);case 1:return min(a,b);case 2:return a b;}
}
void build(int cur,int l,int r,int op){if(l r) st[cur][op] a[l];else{int mid (r l) /2;build(cur*2,l,mid,op);build(cur*21,mid 1,r,op);st[cur][op] ops(st[cur*2][op],st[cur*21][op],op);}
}
void modify(int cur,int l,int r,int pos,int val,int op){if(l r) st[cur][op] val;else{int mid (l r)/2;if(pos mid) modify(cur*2,l,mid,pos,val,op);else modify(cur*2 1,mid 1,r,pos,val,op);st[cur][op] ops(st[cur*2][op],st[cur*21][op],op);}
}
int query(int cur,int l,int r,int x,int y,int op){if(x l y r) return st[cur][op];int mid (lr)/2,res -INF;if(y mid) res query(cur*2,l,mid,x,y,op);else if(x mid){res query(cur*2 1,mid 1,r,x,y,op);}else{int ls query(cur * 2, l, mid, x, y,op); int rs query(cur * 2 1, mid 1, r, x, y,op); res ops(ls,rs,op);}return res;
}
int main(){scanf(%d%d,n,q);for(int i 1;i n;i){scanf(%d,a[i]);}build(1,1,n,0);build(1,1,n,1);build(1,1,n,2);while(q--){int opt,x,y;scanf(%d%d%d,opt,x,y);if(opt 1){modify(1,1,n,x,a[y],0);modify(1,1,n,x,a[y],1);modify(1,1,n,x,a[y],2);modify(1,1,n,y,a[x],0);modify(1,1,n,y,a[x],1);modify(1,1,n,y,a[x],2);swap(a[x],a[y]);}else{int ma query(1,1,n,x,y,0);int mi query(1,1,n,x,y,1);int s (mami)*(ma-mi1)/2;if(s query(1,1,n,x,y,2)){coutYESendl;}else{coutNOendl;}}}return 0;
}
