分块板子（（N+Q）*（根号N））

谁践踏了优雅 2022-03-16 08:24 195阅读 0赞

#include<cstdio>
    #include<iostream>
    #include<algorithm>
    #include<cmath>
    using namespace std;
    int data[6000000],l[500000],r[500000],pos[500000],add[500000],n,m,t;
    long long sum[200000];
    int change(int l1,int r1,int d){
    	int pl=pos[l1],pr=pos[r1];
    	if(pl==pr){
    		for(int i=l1;i<=r1;i++)data[i]++;
    		sum[pl]+=d*(r1-l1+1);
    	}else{
    		for(int i=pl+1;i<=pr-1;i++)add[i]+=d;
    		for(int i=l1;i<=r[pl];i++)data[i]+=d;
    		sum[pl]+=(r[pl]-l1+1)*d;
    		for(int i=l[pr];i<=r1;i++)data[i]+=d;
    		sum[pr]+=(r1-l[pr]+1)*d;
    	}//是小块朴素，大段维护的思想 
    }
    int ask(int l1,int r1){
    	int pl=pos[l1],pr=pos[r1];
    	long long res=0;
    	if(pl==pr){
    		for(int i=l1;i<=r1;i++)res+=(data[i]+add[pl]);		
    	}else{
    		for(int i=pl+1;i<=pr-1;i++)res+=(sum[i]+add[i]*(r[i]-l[i]+1));
    		for(int i=l1;i<=r[pl];i++)res+=(data[i]+add[i]);
    		for(int i=l[pr];i<=r1;i++)res+=(data[i]+add[i]);
    	}
    	return res;
    }
    int main(){
    	scanf("%d%d",&n,&m);
    	for(int i=1;i<=n;i++)scanf("%d",&data[i]);
    	//预处理左右断点 
    	t=sqrt(n);
    	for(int i=1;i<=t;i++){
    		l[i]=(i-1)*sqrt(n)+1;
    		r[i]=i*sqrt(n);
    	}
    	if(r[t]<n){
    		t++;
    		l[t]=r[t-1]+1;r[t]=n;
    	}
    	//预处理每个点在哪一段，并且求出每一段的和 
    	for(int i=1;i<=t;i++){
    		for(int j=l[i];j<=r[i];j++){
    			pos[j]=i;
    			sum[i]+=data[j];
    		}
    	} 
    	char c;
    	int x,y,d;
    	while(m--){
    		cin>>c;
    		if(c=='C'){
    			cin>>x>>y>>d;
    			if(x>y)swap(x,y);
    			change(x,y,d);
    		}else{
    			cin>>x>>y;
    			cout<<ask(x,y);
    		}
    	}	
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，195人围观）

还没有评论，来说两句吧...

相关阅读

相关【板子】分块解决线段树问题

不得不说，分块思想是真的帅啊 [P3372 【模板】线段树 1 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)][P3372 _ 1 - _ _ _ _lu

小鱼儿/ 2024年03月25日 22:29/ 0 赞/ 80 阅读

相关字节1-2 计算根号算法√n

√3 的值是1.7320508075689 public class Test27 { public static void main(String[

秒速五厘米/ 2022年11月04日 01:38/ 0 赞/ 237 阅读

相关浅谈基础根号算法——分块

[https://www.luogu.org/blog/48265/qian-tan-ji-chu-gen-hao-suan-fa-fen-kuai][https_www.lu

你的名字/ 2022年05月09日 08:08/ 0 赞/ 278 阅读

相关分块板子（（N+Q）*（根号N））

include<cstdio> include<iostream> include<algorithm> include<cmath>

谁践踏了优雅/ 2022年03月16日 08:24/ 0 赞/ 196 阅读

相关 taijin板子

include<bits/stdc++.h> using namespace std; int intdex,low[10000],dfn[10000]

ゝ一世哀愁。/ 2022年03月10日 04:48/ 0 赞/ 236 阅读

相关倍增板子

题目：给定一个序列a\[ \]，共 N 个正数，现有 M 次询问，每次给出一个 T ，需要求出最大的 k ，满足Σki=1a\[i\]<=TΣi=1ka\[i\]<=T。方

左手的ㄟ右手/ 2022年03月09日 00:18/ 0 赞/ 221 阅读

相关分块

　　晚上脑子涨涨的，就总结一下最近写的分块入门9题吧。以下全是个人浅薄理解。　　分块，一般就是把一组数据分成sqrt(n)块，然后根据题目要求，对其进行维护。基本要写的就是

淩亂°似流年/ 2021年12月07日 14:11/ 0 赞/ 330 阅读

相关整除分块（数论分块）

转载自[此博客][Link 1] 整除分块：给定n，求（Σd=1n ⌊n /d⌋）%998244353，n<=1e14 直接枚举会爆考虑优化：我们发现

绝地灬酷狼/ 2021年11月01日 03:40/ 0 赞/ 391 阅读

相关 dijkstra板子

include<iostream> include<queue> include<memory.h> using namespace std;

矫情吗；*/ 2021年07月16日 22:45/ 0 赞/ 448 阅读

相关 kruskal板子

include<iostream> include<algorithm> using namespace std; typedef long l

╰+哭是因爲堅強的太久メ/ 2021年07月16日 22:18/ 0 赞/ 454 阅读