浅说线性差分和树上差分
目录[*]线性差分
[*]正常思路
[*]差分思路
[*]二维差分的定义
[*]二维差分的解释
[*]例题1 地毯
[*]树上差分引入
[*]点差分
[*]例题1——wwx的出玩
[*]分析与解答
[*]例题2——松鼠的新家
[*]分析与解答
[*]边差分
[*]例题1——边差分模版
[*]分析与解答
[*]例题2——运输计划
[*]分析与解答
线性差分
当我们这里有\(n\)个数，现在我要对其中一段进行操作，每次可能加上一个数，也有可能减去一个数，请输出最终的数列。
(\(0\le n \le 10^6\))
正常思路
我们正常来看，如果想要对一个区间进行操作，我们只能遍历这个区间，一个一个的去修改，但是这样的的时间复杂度是\(O(n^2)\)，是过不了的，所以我们要换个思路。（当然如果你只想骗点分也是可以的）
#includeusing namespace std;const int INF=1e7;int aint main(){ int n,m; cin>>n>>m; for (int i=1;i>a; } for (int i=1;i>l>>r>>x; for (int j=l;j>m; for (int i=1;i>a; b=a-a;//计算差分数组 } for (int i=1;i>l>>r>>c; b+=c;//核心代码 b-=c; } for (int i=1;ia; b=a-a; } for (int i=1;i>x>>y>>z; b+=z; b-=z; } for (int i=1;ia; if (i==1)continue; long long c=a-a;//求解差值 if (c>0)ans1+=c;//判断是正是负 else ans2+=abs(c); } coutx1>>y1>>x2>>y2; mp++; mp--; mp--; mp++; } for (int i=1;i>v>>x; int root=lca(u,v); p+=x,p+=x,p-=2*x; } get(1,-1); coutn>>m; for (int i=1;i>u>>v>>w; mp.push_back({v,w}); mp.push_back({u,w}); maxlen=max(maxlen,w);//找到最大的边来求上下边界的值 } deep=1; prepare(1,-1); for (int i=1;i>a>>b; dis=lca_length(a,b);//维护路径 maxtot=max(dis,maxtot);//找到最大的路径来求上下边界的值 } int l=maxtot-maxlen,r=300000000; while (l>1; for (int i=1;imid){//不符合条件，开始差分 int root=lca_root(a,b); p]++,p]++,p-=2; tim++;//记录次数 } } if (tim==0){//如果都符合，那么当前答案自然可以 ans=mid; r=mid-1; continue; } get(1,-1);//求子树和 if (maxtot-maxn 喜欢鼓捣这些软件，现在用得少，谢谢分享！ 感谢分享 东西不错很实用谢谢分享 感谢发布原创作品，程序园因你更精彩
页:
[1]