首页 > 代码库 > hdu 4902 线段树+逆向模拟
hdu 4902 线段树+逆向模拟
http://acm.hdu.edu.cn/showproblem.php?pid=4902
出n个数,然后对这n个数进行两种操作:
如果是 1 l r x,则把 [l, r] 区间里面的每一个数都变为x;
如果是 2 l r x,则 比较 [l, r]区间里的数a_i和x的大小,如果a_i > x,把a_i变为a_i和x的最大公约数。
最后输出这n个数最终的值。
线段树可搞...但是没必要!...
线段树,每个结点多一个lazy表示该位置以下区间是否数字全相同,然后每次延迟操作,最后输出的时候单点查询即可
#include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <string> #include <vector> #include <queue> #include <iostream> #include <algorithm> using namespace std; #define RD(x) scanf("%d",&x) #define RD2(x,y) scanf("%d%d",&x,&y) #define clr0(x) memset(x,0,sizeof(x)) typedef long long LL; const int N = 100005; struct node { int lazy,v; }s[N<<3]; int c[N]; void updata(int root){ s[root].v = max(s[root<<1].v,s[root<<1|1].v); } void build(int l,int r,int root) { s[root].lazy = 0; if(l == r){ s[root].v = c[l]; return; } int mid = (l+r)>>1; build(l,mid,root<<1); build(mid+1,r,(root<<1)+1); updata(root); } int gcd(int a,int b) { if(b==0) return a; return gcd(b,a%b); } void changee(int l,int r,int root,int ll,int rr,int v) { if (l > rr || r < ll) return; if (ll <= l && rr >= r){ s[root].lazy = 1; s[root].v = v; return; } if(s[root].lazy){ s[root<<1].lazy = 1; s[root<<1].v = s[root].v; s[root<<1|1].lazy = 1; s[root<<1|1].v = s[root].v; s[root].lazy = 0; } int mid = (l+r)>>1; changee(l,mid,root<<1,ll,rr,v); changee(mid+1,r,(root<<1)+1,ll,rr,v); updata(root); } void query(int l , int r , int root){ if(s[root].lazy || l == r){ for(int i = l;i <= r;++i) printf("%d ",s[root].v); return; } int mid = (l+r)>>1; query(l,mid,root<<1); query(mid+1,r,(root<<1)+1); } void change(int l , int r , int root, int ll , int rr , int x){ if (s[root].v < x || l > rr || r < ll) return; if (s[root].lazy && ll <= l && rr >= r){ s[root].v = gcd(x,s[root].v); return; } if(l == r){ s[root].v = gcd(x,s[root].v); return; } if(s[root].lazy){ s[root<<1].lazy = 1; s[root<<1].v = s[root].v; s[root<<1|1].lazy = 1; s[root<<1|1].v = s[root].v; s[root].lazy = 0; } int mid = (l+r)>>1; change(l,mid,root<<1,ll,rr,x); change(mid+1,r,(root<<1)+1,ll,rr,x); updata(root); } int main() { int Q,n,_;RD(_); while(_--){ RD(n); for(int i = 1;i <= n;++i) RD(c[i]); build(1,n,1); RD(Q); int l,r,q,x; while(Q--){ scanf("%d%d%d%d",&q,&l,&r,&x); if(q == 1) changee(1,n,1,l,r,x); else change(1,n,1,l,r,x); } query(1,n,1); puts(""); } return 0; }
其实逆向模拟即可,求每一个数的最终结果时,就可以用栈从后向前压入每个操作,直到遇到1操作,或者没有遇到1操作,则初值就为输入的a_i,然后把站内元素依次取出操作即可
#include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <string> #include <queue> #include <stack> #include <iostream> #include <algorithm> using namespace std; #define RD(x) scanf("%d",&x) #define RD2(x,y) scanf("%d%d",&x,&y) #define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z) #define clr0(x) memset(x,0,sizeof(x)) typedef long long LL; const int maxn = 1e5+5; struct opertion { int t, l, r; int x; }o[maxn]; int a[maxn]; int gcd(int a,int b) { if(b==0) return a; return gcd(b,a%b); } int main() { int _, n, i, j, Q; RD(_); while(_--) { RD(n); for(i = 1; i <= n; i++) RD(a[i]); RD(Q); for(i = 0; i < Q; i++) RD3(o[i].t,o[i].l,o[i].r),RD(o[i].x); for(i = 1; i <= n; i++) { stack<int> s; int flag = 0; for(j = Q - 1; j >= 0; j--) { if(i >= o[j].l && i <= o[j].r) { s.push(o[j].x); if(o[j].t == 1) { flag = 1; break; } } } if(!flag) //没有遇到1操作 s.push(a[i]); while(s.size() > 1) { int ans = s.top(); s.pop(); int tmp = s.top(); s.pop(); if(ans > tmp) ans = gcd(ans, tmp); s.push(ans); } printf("%d ", s.top()); } puts(""); } return 0; }
hdu 4902 线段树+逆向模拟
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。