c – 具有延迟传播时间限制问题的段树
发布时间:2020-12-16 06:56:50 所属栏目:百科 来源:网络整理
导读:以下是使用具有延迟传播的Segment Tree的 http://www.spoj.pl/problems/LITE/的实现.我是新的细分树,我不明白为什么我得到TLE.有人可以看一下,帮我纠正错误吗? #include iostream#include iostream#include cstdio#include cstring#define MAX 100000using
以下是使用具有延迟传播的Segment Tree的
http://www.spoj.pl/problems/LITE/的实现.我是新的细分树,我不明白为什么我得到TLE.有人可以看一下,帮我纠正错误吗?
#include <iostream> #include <iostream> #include <cstdio> #include <cstring> #define MAX 100000 using namespace std; int M[2*MAX+1]; int flag[2*MAX+1]; int count; void refresh(int begin,int end,int n) { M[n] = end-begin+1 - M[n]; flag[n]=0; flag[n*2] =!flag[n*2]; flag[n*2+1] =!flag[n*2+1]; } void update(int begin,int i,int j,int n=1) { if(flag[n]) { refresh(begin,end,n); } if(begin>=i && end<=j) { if(!flag[n]) { refresh(begin,n); } flag[n] = 0; return; } else if(begin>=end) { return; } else { int mid = (begin+end)>>1; if(i<=mid) { update(begin,mid,i,j,n*2); } if(j>mid) { update(mid+1,n*2+1); } if(flag[2*n]) { refresh(begin,2*n); } if(flag[2*n+1]) { refresh(mid+1,2*n+1); } M[n] = M[n*2]+ M[n*2+1]; } } int query(int begin,n); } if(begin>=i && end<=j) { return M[n]; } if(begin>=end) { return 0; } int mid = (begin+end)>>1; int l=0,r=0; if(i<=mid) { l = query(begin,n*2); } if(j>mid) { r = query(mid+1,n*2+1); } if(flag[2*n]) { refresh(begin,2*n); } if(flag[2*n+1]) { refresh(mid+1,2*n+1); } M[n] = M[n*2]+ M[n*2+1]; return l+r; } int main() { memset(M,sizeof M); int n,m,a,b,c; scanf("%d%d",&n,&m); for(int i=0; i<m; i++) { scanf("%d%d%d",&a,&b,&c); if(a==0) { update(1,n,c); } else { printf("%dn",query(1,c)); } } return 0; } 解决方法
M [节点] ^ = 1;可能比M [node] =(M [node] == 0)?1:0;和(begin end)>> 1快于(begin / end)/ 2,但不是很相关
LE:尝试使内联递归函数运行得更快.我认为它几次解开递归并且工作速度更快一点.也许将参数作为参考发送将使其运行得更快,尝试一下.如果正确选择了测试用例,你仍然无法通过这种技巧通过测试,但它有时会有所帮助. (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |