题目传送门:http://uoj.ac/problem/218
数据生成器:http://paste.ubuntu.com/20456908/
这一道题目,考试的时候,还是想要A掉来着,结果wa得只剩10分QAQ
™我的自定义测试,那么大的数据都没有wa
考试的时候,我的做法是:
单独一棵线段树用来处理询问
然后再用一个二维线段树来维护堆栈
第一维是时间,用来二分最近最近的有效操作
第二维是车站,用来支持二分的查询动作
时间复杂度:O(nlog^2(n))
std的做法是:
任然单独搞一棵线段树来对付询问
对于操作,直接上函数式线段树QAQ
时间复杂度:O(nlogn)
至今都觉得还是我的做法最自然
但他们都说函数式线段树最自然QAQ
#include<iostream> #include<cstdio> using namespace std; const int MAXN = 500000+9; int n,m,ty,last_ans,arr[MAXN]; inline int read(){ char c=getchar(); int buf=0,f=1; while (c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0'){buf=buf*10+c-'0';c=getchar();} return (buf*f+last_ans*ty) % n + 1; } namespace Segment_Tree{ #define SEG Segment_Tree const int N = MAXN*4; int tag[N],sum[N],tm[N],ans_tmp,L,R,DEL; inline void push_down(int w, int l, int r, int mid){ tag[w*2] = tag[w*2+1] = tag[w]; sum[w*2] = (mid-l)*arr[tag[w]]; sum[w*2+1] = (r-mid+1)*arr[tag[w]]; tag[w] = 0; } void query(int w, int l, int r){ if (L <= l && r <= R) ans_tmp += sum[w]; else { int mid = (l + r + 1) / 2; if (tag[w]) push_down(w,l,r,mid); if (L < mid) query(w*2,l,mid-1); if (R >= mid) query(w*2+1,mid,r); } }inline int query(int l, int r){ans_tmp=0;L=l,R=r;query(1,1,n);return ans_tmp;} void Modify(int w, int l, int r){ if (L <= l && r <= R) tag[w] = DEL, sum[w] = (r-l+1)*arr[DEL]; else { int mid = (l + r + 1) / 2; if (tag[w]) push_down(w,l,r,mid); if (L < mid) Modify(w*2,l,mid-1); if (R >= mid) Modify(w*2+1,mid,r); sum[w] = sum[w*2] + sum[w*2+1]; } }inline void modify(int l, int r, int del){L=l,R=r,DEL=del;Modify(1,1,n);} inline int index(int pos){ int w = 1, l = 1, r = n, mid; while (l < r) { if (tag[w]) return tag[w]; else { mid = (l + r + 1) / 2; if (pos < mid) w = w*2, r = mid-1; else w = w*2+1, l = mid; } } return tag[w]; } }; namespace Persistent_Segment_Tree{ #define PST Persistent_Segment_Tree const int N = 20000000; int tag[N],root[N],ch[N][2],tot,cnt,L,R,DEL; inline int query(int tm, int pos) { if (tm < 1) return 0; else { int w = root[tm], l=1, r=n, mid; while (l < r) { if (tag[w]) return tag[w]; else { mid = (l + r + 1) / 2; if (pos < mid) w = ch[w][0], r = mid-1; else w = ch[w][1], l = mid; } } return tag[w]; } } inline void push_down(int w){ for (int i=0;i<=1;i++) if (!ch[w][i]) ch[w][i] = ++cnt; for (int i=0;i<=1;i++) tag[ch[w][i]] = tag[w]; tag[w] = 0; } void Modify(int pre, int &w, int l, int r, int tg){ w = ++cnt; ch[w][1] = ch[pre][1]; ch[w][0] = ch[pre][0]; tag[w] = tg?tg:tag[pre]; if (L <= l && r <= R) tag[w] = DEL; else { int mid = (l + r + 1) / 2; if (L < mid) Modify(ch[pre][0],ch[w][0],l,mid-1,tag[w]); else if (tag[w]) ch[w][0] = ++cnt, tag[cnt] = tag[w]; if (mid <= R) Modify(ch[pre][1],ch[w][1],mid,r,tag[w]); else if (tag[w]) ch[w][1] = ++cnt, tag[cnt] = tag[w]; tag[w] = 0; } } inline int modify(int l, int r, int val, bool type){ L = l, R = r, DEL = val; Modify(root[tot], root[(tot+type)], 1, n, 0); tot += type; return tot; } }; int main(){ scanf("%d%d%d",&n,&m,&ty); for (int i=1,type,l,r,del;i<=m;i++){ scanf("%d",&type); if (type == 1) { l = read(); r = read(); if (l > r) swap(l, r); printf("%d\n",last_ans=SEG::query(l,r)); } else if (type == 2) { l = read(); int tmp = SEG::index(l); int nv = PST::query(tmp-1,l); PST::modify(l,l,nv,0); SEG::modify(l,l,nv); } else { l = read(); r = read(); scanf("%d",&del); if (l > r) swap(l, r); int tmp = PST::modify(l,r,PST::tot+1,1); arr[tmp] = del; SEG::modify(l, r, tmp); } } return 0; }
楼下是疯子。哈哈
Really appreciate you sharing this article post.Really thank you! Fantastic.