临泉网站建设,上海发布公众号官网,网络服务提供者不得为未满多少岁开展工作,angularjs 网站开发传送门:牛客
题目描述:
题目latex公式较多,此处省略
输入:
10 6
1 1 1
2 4 6
1 3 2
2 5 7
1 6 10
2 1 10
输出:
3
5
26这道题让我体验到的线段树相对于树状数组的常数巨大
我们倘若直接用单点修改的话#xff0c;如果D过小比如1那么我们足足要加n次#xff0c;时间复杂度爆…传送门:牛客
题目描述:
题目latex公式较多,此处省略
输入:
10 6
1 1 1
2 4 6
1 3 2
2 5 7
1 6 10
2 1 10
输出:
3
5
26这道题让我体验到的线段树相对于树状数组的常数巨大
我们倘若直接用单点修改的话如果D过小比如1那么我们足足要加n次时间复杂度爆炸。 那如果我们把每次要相加的记录下来lazy[D]K那么在我们计算和时
for (int i1;in;i)ans(b/i - (a-1)/i)*lazy[i]我们发现我们同样复杂度无法接受
所以对于本题来说,我们需要有一个分块的想法,也就是找一个界限,在界限的两边采用不同的算法,使得我们的总体复杂度可以接受.我们设这个度为S.我们发现我们的模数越大,显然对直接暴力修改时越有利的,因为我们需要修改的点就越小.反之我们应选用记录lazy的方式
那么对于第一种方法来说,我们的最坏复杂度为n/S∗logn∗mn/S*logn*mn/S∗logn∗m 对于第二种方法来说,我们的最坏复杂度为S∗mS*mS∗m 我们的总体复杂度为n/S∗logn∗mS∗mn/S*logn*mS*mn/S∗logn∗mS∗m(实际上应该是小于这个值的,因为操作总数为m,此时为了方便,我们将两种方法都当做m) 此时显然运用均值不等式的小知识,我们会发现当SSSn∗logn\sqrt{n*logn}n∗logn时取到最小值,此时我们的复杂度大概为1e81e81e8左右
此时我就要吐槽了,牛客上对于这道题,几乎所有的解法(包括题解),都是直接取用SSSn\sqrt{n}n,此时的复杂度应该是m∗n∗lognm*\sqrt{n}*lognm∗n∗logn,达到了1e9多了,然而他们使用树状数组是可以直接过的(还跑的飞快).嗯,我可以理解,毕竟时限开到了2s2s2s,牛客跑的快,可能仍然可以跑过去.但是我TM使用线段树就被卡了,我直接想大骂,难道就没人尊重线段树爱好者吗(虽然线段树常数确实较大),想用线段树的话必须要用上述的最优的分界点S
并且因为直接计算n∗logn\sqrt{n*logn}n∗logn速度较慢所以我们不能把这个式子放在循环里,这样依旧会Tle,所以我们需要提前计算出这个值(当时我还以为这道题卡定线段树了呢,即使用了最优分界点仍然过不去…)
下面是具体的代码部分:
#include bits/stdc.h
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt1
#define rs rt1|1
#define lson l,mid,rt1
#define rson mid1,r,rt1|1
inline ll read() {ll x0,w1;char chgetchar();for(;ch9||ch0;chgetchar()) if(ch-) w-1;for(;ch0ch9;chgetchar()) xx*10ch-0;return x*w;
}
#define int long long
#define maxn 1000000
const double eps1e-8;
#define int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
struct Segment_tree{int l,r,sum;
}tree[maxn*4];
int n,m;
void pushup(int rt) {tree[rt].sumtree[ls].sumtree[rs].sum;
}
void build(int l,int r,int rt) {tree[rt].ll;tree[rt].rr;if(lr) return ;int mid(lr)1;build(lson);build(rson);
}
void update(int pos,int v,int rt) {if(tree[rt].lpostree[rt].rpos) {tree[rt].sumv;return ;}int mid(tree[rt].ltree[rt].r)1;if(posmid) update(pos,v,ls);else update(pos,v,rs);pushup(rt);
}
int query(int l,int r,int rt) {if(tree[rt].lltree[rt].rr) {return tree[rt].sum;}int mid(tree[rt].ltree[rt].r)1;if(rmid) return query(l,r,ls);else if(lmid) return query(l,r,rs);else return query(l,mid,ls)query(mid1,r,rs);
}
int Add[maxn];
signed main() {nread();mread();build(root);double sqsqrt((double)n*log((double)n));for(int i1;im;i) {int optread();if(opt1) {int dread(),kread();if(dsq) {
// coutd sqrt((double)n*log((double)n))endl;for(int id;in;id) {update(i,k,1);}}else {Add[d]k;}}else {int lread(),rread();int ansquery(l,r,1);for(int i1;isq;i){ansAdd[i]*(r/i-(l-1)/i);}printf(%lld\n,ans);}}return 0;
}
