首页 > 其他分享 >[P4145 上帝造题的七分钟 2 / 花神游历各国]题解

[P4145 上帝造题的七分钟 2 / 花神游历各国]题解

时间:2023-04-29 16:46:48浏览次数:45  
标签:int 题解 ll 七分钟 maxn P4145 block

P4145 上帝造题的七分钟 2 / 花神游历各国

题目描述

分析

一开始在思考有没有一个数学公式来处理每一个开方的操作
但发现数据的\(\le 10^{12}\)
那么最多开六次就变成1了(突破口)
这样每一个数的有用操作只有6次
其他就全部是1

很显然,我们可以去记录每一段是否全为1
再用线段树、分块或树状数组解决了

由于我才学了分块,所以就用分块吧

代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int maxn=1e5+10;
int block,n,m,op,l,r,id[maxn];
ll a[maxn],tag[1005],sum[1005];

void ssqrt(int x){
  ll res=0;
  int L=(x-1)*block+1,R=x*block;
  bool flag=true;
  for(int i=L;i<=R;i++){
  	if(a[i]==1){res++;continue;}
  	a[i]=(ll)floor(sqrt(a[i]));
  	if(a[i]!=1) flag=false;
  	res+=a[i];
  }
  if(flag) tag[x]=1;
  sum[x]=res;
}

void change(int l,int r){
  //1.左散块
  for(int i=l;i<=min(r,id[l]*block);i++)
    sum[id[i]]-=a[i],a[i]=(ll)floor(sqrt(a[i])),sum[id[i]]+=a[i];
  if(id[l]==id[r]) return ; 
  //2.中间的整块
  for(int i=id[l]+1;i<=id[r]-1;i++)
    if(!tag[i]) ssqrt(i);
  //3.右散块 
  for(int i=(id[r]-1)*block+1;i<=r;i++)
    sum[id[i]]-=a[i],a[i]=(ll)floor(sqrt(a[i])),sum[id[i]]+=a[i];
}

ll query(int l,int r){
  ll res=0;
  //1.左散块
  for(int i=l;i<=min(r,id[l]*block);i++)
    res+=a[i];
  if(id[l]==id[r]) return res;
  //2.中间的整块
  for(int i=id[l]+1;i<=id[r]-1;i++) res+=sum[i];
  //3.右散块 
  for(int i=(id[r]-1)*block+1;i<=r;i++) res+=a[i];
  return res;
}

int main(){
  /*2023.4.29 hewanying P4145 上帝造题的七分钟 2 / 花神游历各国 分块*/ 
  scanf("%d",&n);
  block=(int)floor(sqrt(n));
  for(int i=1;i<=n;i++){
  	id[i]=(i-1)/block+1;
  	scanf("%lld",&a[i]);
  	sum[id[i]]+=a[i];
  }
  scanf("%d",&m);
  for(int i=1;i<=m;i++){
  	scanf("%d%d%d",&op,&l,&r);
  	if(l>r) swap(l,r);
  	if(op==0) change(l,r);
  	else printf("%lld\n",query(l,r));
  }
  return 0;
}

总结

1.对于那些看似没有公式或方法进行区间处理的,我们可以考虑计算每个值被有效操作的次数,一般情况这样的次数会很小,从而直接可以暴力枚举
2.区间数据结构对于每一个整块的操作一定是\(O(1)\)的,可以从这一点下手

标签:int,题解,ll,七分钟,maxn,P4145,block
From: https://www.cnblogs.com/hewanying0622/p/17364198.html

相关文章

  • CodeForces-858#C 题解
    正文♦最坏时间复杂度:\(\mathcal{O}(\lvertS\rvert)\)本题十分简单,但请注意两个条件要同时满足。因为要求分割的次数越少越好,所以只要连续的辅音字母长度不大于2就不需要分割。由于辅音字母太多,只需要标记元音字母即可。#include<iostream>#include<string>#include<cst......
  • 【题解】P3920 [WC2014]紫荆花之恋
    思路点分树+根号重构+*高速平衡树。点分树的两种常见用法无非是直接做和路径有关的暴力还有处理这种有关单点和整树的问题,后者的另一个经典题目是P3241[HNOI2015]开店。回到这个题目,处理路径考虑先上点分治,暂时不考虑强制在线的限制。因为每次加上一个新点,所以可以考......
  • CF1656F Parametric MST 题解
    为了便于解题,先对\(a\)数组从小到大进行排序。首先,根据定义可以得出总价值的表达式:\[\begin{aligned}W&=\sum\limits_{(u,v)\inE}[a_ua_v+t(a_u+a_v)]\\&=\sum\limits_{(u,v)\inE}a_ua_v+t\sum\limits_{(u,v)\inE}(a_u+a_v)\end{aligned}\]接着,我们需要发现一个比较......
  • P6818 [PA2013]Działka 题解
    P6818[PA2013]Działka前言我太菜了。。。。对着jiangly大佬的题解研究了一下午研究了一下午才搞出来(泪目。作为一个蒟蒻,我就详细的讲一下我对与本题的理解。题意本题的的题意描述的还是比较明了。在二维坐标系中,输入\(n\)个点\(m\)次询问,每次询问,给出一个矩阵,......
  • 天池编程大赛周赛-Character deletion 题解
    题目描述EntertwostringsanddeleteallcharactersinthesecondstringfromthefirststringStringcontainsspaces$1\leqlen(str),len(sub)\leq10^5$示例示例1:Input:str=”Theyarestudents”,sub=”aeiou”Output:”Thyrstdnts”来源:九章算法链接:ht......
  • P3573 [POI2014]RAJ-Rally 题解
    非常好题目,爱来自xc。看到有向无环图,想到拓扑序。通过拓扑序,可以轻松求出以每个点为起点的最长路\(disS\)与每个点为终点的最长路\(disF\)。如何求总共的最长路?在\(disS,disF,disS_u+1+disF_v((u,v)\inE)\)中取最大值即可。注意最后一项,表示将连边的二点值相加。......
  • 题解 CF1264D1
    前言数学符号约定:\(\dbinom{n}{m}\):表示\(n\)选\(m\)。如非特殊说明,将会按照上述约定书写符号。题目分析:考虑题目的问题弱一点的版本,假设此时我们的括号序列是确定的如何求其括号匹配的最深深度。如果你有些许dp基础的话,不难想到如下做法:考虑位置\(i\),将区间\([1,......
  • 题解 CF1264D2
    前言建议大家看一下我对于D1的题解(传送门)后再看本题解,本题解是基于那篇题解的基础上书写的。数学符号约定\(\dbinom{n}{m}\):表示\(n\)选\(m\)。如非特殊说明,将会按照上述约定书写符号。题目分析首先引用一下D1的答案:\(\displaystyle\sum_{i=1}^n\displaystyle\sum_{......
  • [ARC125E] Snack 题解
    不难发现一个较简单的网络流模型:源点向所有糖果\(i\)连\(a_i\)的容量;所有糖果向所有人\(i\)连\(b_i\)的容量;所有人\(i\)向汇点连\(c_i\)的容量。但第二步中建出的边数达到了惊人的\(O(nm)\),显然过不去。考虑优化。从最大流角度优化较困难,由于最大流等价于最小......
  • P4423 题解
    前言题目传送门!更好的阅读体验?刚学分治就来写篇题解纪念一下,其实和平面最近点对一样的(总共四倍经验!)。思路根据P7883的分治思路,这题我们可以考虑用相似的方法解决。首先将点集按\(x\)坐标从小到大排序。然后分治。对于\(\left[l,r\right]\)区间,分治为\(\left[l,mid......