[Ynoi2019]魔法少女网站

2024-03-16 22:48
文章标签 网站 魔法 少女 ynoi2019

本文主要是介绍[Ynoi2019]魔法少女网站,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

魔法少女网站

题解

魔鬼卡常题,我卡了一周的常

由于我们查询的是最大值不大于 x x x的区间个数,我们可以考虑将原序列转换成 0 / 1 0/1 0/1序列,小于等于 x x x的位置为 1 1 1,大于 x x x的位置为 0 0 0,那么我们要求的就是全为 1 1 1的区间个数。
但很明显我们不可能得到整个 0 / 1 0/1 0/1序列后再检查一遍求出答案,我们的在过程中记录下全为 1 1 1的区间,更新答案。
如果要记录的话我们需要尽量将 0 0 0变成 1 1 1,我们将 1 1 1变成 0 0 0的部分是只能通过回退来处理的。
每次我们将 0 0 0变为 1 1 1相当于连接两个全 1 1 1的段,一个长度为 x x x的段会产生 x + x 2 2 \frac{x+x^2}{2} 2x+x2个子区间,那么我们连接两个长度为 x x x y y y的段带来的答案变化有 ( x + y + 1 ) ( x + y + 2 ) 2 − x ( x + 1 ) 2 − y ( y + 1 ) 2 \frac{(x+y+1)(x+y+2)}{2}-\frac{x(x+1)}{2}-\frac{y(y+1)}{2} 2(x+y+1)(x+y+2)2x(x+1)2y(y+1)
而将 1 1 1变成 0 0 0就只能回退到那个操作在将这个操作逆向回来。

于是我们很快就想到了回滚莫队,我们先将所有的询问按时间排序分块,同一块内的询问再按权值排序。
将所有的数都执行了在这个块之前的操作先全部执行了,反正它们不会影响到我们块内的操作。
由于我们的询问的权值是递增的,所以执行操作后的初始权值对应的点在我们的 0 / 1 0/1 0/1序列中只会不断从 0 0 0变成 1 1 1
但是,有一部分点是有对应操作与它在一个块中,这部分我们是没法提前处理的,我们只能每次将操作对应的点特殊处理一遍,该询问进行完后再将这些操作去掉,这部分是通过回退去掉的。
这样对于每个询问我们都回回退 O ( S ) O\left(S\right) O(S),而我们总共会对 O ( n S ) O\left(\frac{n}{S}\right) O(Sn)个串进行操作,每个块的我们都需要将 n n n个点加进去,就会有个 O ( n ) O\left(n\right) O(n)的复杂度,所以涉及到块的操作我们时间复杂度是 ( n S + n 2 S ) \left(nS+\frac{n^2}{S}\right) (nS+Sn2)的。

但我们的询问时区间的询问是区间询问,我们不能直接通过全局的记录得出我们区间询问的答案。
但我们可以考虑对其进行序列分块以求出答案。
我们对于只存在一个块内部的连续段单独记录答案,在操作过程中就存下来,而块块间的我们就记录下上次出现的位置,直到它不能继续延续时再加入答案。
这样我们求答案的时间复杂度也是 O ( n ( S + n S ) ) O\left(n(S+\frac{n}{S})\right) O(n(S+Sn))

总时间复杂度 $O\left(nS+\frac{n^2}{S}\right)\geqslant $
按理说我们这样的做法就可以轻松过掉了。
但这道题的出题人是 l x l lxl lxl,所以这道题很卡常。
你需要手写STL,fread,fwrite以及其余各种优化,顺便卡一下块长,就可以轻松过掉了。
不过好像就我卡了4页常,63发提交可不是虚的

源码

#include<bits/stdc++.h>
using namespace std;
#define MAXN 300005
#define lowbit(x) (x&-x)
#define reg register
#define pb push_back
#define mkpr make_pair
#define lson (rt<<1)
#define rson (rt<<1|1)
typedef long long LL;
typedef unsigned long long uLL;
const int INF=0x3f3f3f3f;
const int mo=1e9;
const int inv2=499122177;
const int jzm=2333;
const int lim=300000;
const int orG=3,invG=332748118;
const double Pi=acos(-1.0);
const double eps=1e-7;
typedef pair<int,int> pii;
template<typename _T>
_T Fabs(_T x){return x<0?-x:x;}
char gc(){static char buf[1000000],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;}
#define getchar gc
char obuf[1<<22],*opt=obuf+(1<<22);
void pc(const int&ch){*--opt=ch;}
#define putchar pc
template<typename _T>
void read(_T &x){_T f=1;x=0;char s=getchar();while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}x*=f;
}
template<typename _T>
void print(_T x){putchar('\n');while(x>9){putchar((x%10)|'0');x/=10;}putchar(x|'0');}
LL gcd(LL a,LL b){return !b?a:gcd(b,a%b);}
int add(int x,int y,int p){return x+y<p?x+y:x+y-p;}
void Add(int &x,int y,int p){x=add(x,y,p);}
int qkpow(int a,int s,int p){int t=1;while(s){if(s&1LL)t=1ll*a*t%p;a=1ll*a*a%p;s>>=1LL;}return t;}
const int N=MAXN;
int n,m,bl[N],br[N],tim,cd;LL ans[N],wk[N],now[N];
int a[N],al[N],ar[N],sta[N],sd[N],stak,p[N],bk[N];
int vis[N],vp[N],totc,totd,head[N],nxt[N];
struct ming{int opt,l,r,ti,val;bool operator < (const ming &rhs)const{return val<rhs.val;}
}d[N],e[N];
inline void insert(const int ai){a[ai]=1;al[ai]=ar[ai]=ai;int l=ai,r=ai;const int ba=bk[ai];if(a[ai-1]&&bk[ai-1]==ba){l=al[ai-1];now[ba]-=wk[ai-l];ar[al[ai-1]]=ar[ai];al[ai]=al[ai-1];al[ar[ai]]=al[ai];}if(a[ai+1]&&bk[ai+1]==ba){r=ar[ai+1];now[ba]-=wk[r-ai];al[ar[ai+1]]=al[ai];ar[ai]=ar[ai+1];ar[al[ai]]=ar[ai];}now[bk[ai]]+=wk[r-l+1];
}
inline void remove(const int ai){reg int l=ai,r=ai;const int ba=bk[ai];if(a[ai+1]&&bk[ai+1]==ba)al[ar[ai]]=ai+1;if(a[ai-1]&&bk[ai-1]==ba)ar[al[ai]]=ai-1;a[ai]=0;
}
inline void sakura(const int i){for(reg int j=1;j<=n;j++)nxt[j]=head[p[j]],head[p[j]]=j;reg int k=1;sort(d+1,d+totd+1);for(reg int j=1;j<=totd;j++){const int dt=d[j].ti,dv=d[j].val,dl=d[j].l,dr=d[j].r;while(k<=dv){for(reg int k1=head[k];k1;k1=nxt[k1])if(vis[k1]!=i)insert(k1);k++;}stak=ans[dt]=0;for(reg int k1=totc;k1>0;k1--){if(vp[e[k1].l]==dt||e[k1].ti>dt)continue;vp[e[k1].l]=dt;if(e[k1].val<=dv)sta[++stak]=e[k1].l,sd[stak]=now[bk[e[k1].l]],insert(e[k1].l);}for(reg int k1=totc;k1>0;k1--){if(vp[e[k1].l]==dt)continue;if(e[k1].ti<dt)break;vp[e[k1].l]=dt;if(p[e[k1].l]<=dv)sta[++stak]=e[k1].l,sd[stak]=now[bk[e[k1].l]],insert(e[k1].l);}if(bk[dl]==bk[dr]){reg int las=0;for(reg int k1=dl;k1<=dr;k1++)if(a[k1])las++;else ans[dt]+=wk[las],las=0;ans[dt]+=wk[las];}else{reg int las=0;for(reg int k1=dl;k1<=br[bk[dl]];k1++)if(a[k1])las++;else ans[dt]+=wk[las],las=0;for(reg int k1=bk[dl]+1;k1<bk[dr];k1++){reg int tmpl=a[bl[k1]]?ar[bl[k1]]-bl[k1]+1:0;reg int tmpr=a[br[k1]]?br[k1]-al[br[k1]]+1:0;if(tmpl==br[k1]-bl[k1]+1)las+=tmpl;else ans[dt]+=now[k1]+wk[las+tmpl]-wk[tmpl]-wk[tmpr],las=tmpr;}for(reg int k1=bl[bk[dr]];k1<=dr;k1++)if(a[k1])las++;else ans[dt]+=wk[las],las=0;ans[dt]+=wk[las];}while(stak)now[bk[sta[stak]]]=sd[stak],remove(sta[stak--]);}for(reg int j=1;j<=totc;j++)p[e[j].l]=e[j].val;totc=totd=0;for(reg int j=1;j<=n;j++)a[j]=head[j]=0;for(reg int j=1;j<=bk[n];j++)now[j]=0;
}
signed main(){read(n);read(m);tim=1;const int n1=sqrt(n);for(reg int i=1;i<=n;i++)read(p[i]);for(reg int i=1;i<=n;i++)wk[i]=1ll*i*(i+1)/2LL;for(reg int i=1;i<=n;i++){bk[i]=(i+n1-1)/n1;if(!bl[bk[i]])bl[bk[i]]=i;br[bk[i]]=i;}for(reg int i=1;i<=m;i++){reg int opt;read(opt);ans[i]=-1;ming s;if(opt==1){reg int x,y;read(x);read(y);e[++totc]=(ming){1,x,0,i,y};vis[x]=tim;}else{reg int l,r,x;read(l);read(r);read(x);d[++totd]=(ming){2,l,r,i,x};}if(totc+totd==2000||i==m)sakura(tim),tim++;}for(int i=m;i>0;i--)if(ans[i]>=0)print(ans[i]);fwrite(opt,1,obuf+(1<<22)-opt,stdout);return 0;
}

谢谢!!!!

这篇关于[Ynoi2019]魔法少女网站的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/816977

相关文章

速盾高防cdn是怎么解决网站攻击的?

速盾高防CDN是一种基于云计算技术的网络安全解决方案,可以有效地保护网站免受各种网络攻击的威胁。它通过在全球多个节点部署服务器,将网站内容缓存到这些服务器上,并通过智能路由技术将用户的请求引导到最近的服务器上,以提供更快的访问速度和更好的网络性能。 速盾高防CDN主要采用以下几种方式来解决网站攻击: 分布式拒绝服务攻击(DDoS)防护:DDoS攻击是一种常见的网络攻击手段,攻击者通过向目标网

49个权威的网上学习资源网站

艺术与音乐 Dave Conservatoire — 一个完全免费的音乐学习网站,口号是“让每一个人都可以接受世界级的音乐教育”,有视频,有练习。 Drawspace — 如果你想学习绘画,或者提高自己的绘画技能,就来Drawspace吧。 Justin Guitar — 超过800节免费的吉他课程,有自己的app,还有电子书、DVD等实用内容。 数学,数据科学与工程 Codecad

BT天堂网站挂马事件后续:“大灰狼”远控木马分析及幕后真凶调查

9月初安全团队披露bt天堂网站挂马事件,该网站被利用IE神洞CVE-2014-6332挂马,如果用户没有打补丁或开启安全软件防护,电脑会自动下载执行大灰狼远控木马程序。 鉴于bt天堂电影下载网站访问量巨大,此次挂马事件受害者甚众,安全团队专门针对该木马进行严密监控,并对其幕后真凶进行了深入调查。 一、“大灰狼”的伪装 以下是10月30日一天内大灰狼远控的木马样本截图,可以看到该木马变种数量不

PHP抓取网站图片脚本

方法一: <?phpheader("Content-type:image/jpeg"); class download_image{function read_url($str) { $file=fopen($str,"r");$result = ''; while(!feof($file)) { $result.=fgets($file,9999); } fclose($file); re

使用WebP解决网站加载速度问题,这些细节你需要了解

说到网页的图片格式,大家最常想到的可能是JPEG、PNG,毕竟这些老牌格式陪伴我们这么多年。然而,近几年,有一个格式悄悄崭露头角,那就是WebP。很多人可能听说过,但到底它好在哪?你的网站或者项目是不是也应该用WebP呢?别着急,今天咱们就来好好聊聊WebP这个图片格式的前世今生,以及它值不值得你花时间去用。 为什么会有WebP? 你有没有遇到过这样的情况?网页加载特别慢,尤其是那

黑客为什么不黑赌博网站来搞米?

攻击了,只是你不知道而已! 同样,对方也不会通知你,告诉你他黑了赌博网站。 攻击赌博网站的不一定是正义的黑客,也可能是因赌博输钱而误入歧途的法外狂徒。之前看过一个警方破获的真实案件:28岁小伙因赌博无法提款自学成为黑客,攻击境外博彩网站日进万元,最终因涉嫌非法控制计算机信息系统罪被捕。 我见过很多因赌博输钱想请黑客帮忙渗透网站的人,在被拒后,同样也有人生出极端心理,问我怎么学习黑客,想学成之

提升PrestaShop外贸电商网站安全的几款行业必备工具

提升PrestaShop外贸电商网站安全的几款行业必备工具 PrestaShop发展历程 PrestaShop是一款优秀且强大的外贸开源电商软件,我们开始使用PrestaShop始于2009年,那时PrestaShop还是0.9版本:界面清新,性能强悍,扩展友好等特性,既没有Magento的笨重,也没有ZenCart的古老,更没有OpenCart的脆弱,因此PrestaShop如雨后春笋,迅速

推荐练习键盘盲打的网站

对于初学者来说,以下是一些推荐的在线打字练习网站: 打字侠:这是一个专业的在线打字练习平台,提供科学合理的课程设置和个性化学习计划,适合各个水平的用户。它还提供实时反馈和数据分析,帮助你提升打字速度和准确度。 dazidazi.com:这个网站提供了基础的打字练习,适合初学者从零开始学习打字。 Type.fun打字星球:提供了丰富的盲打课程和科学的打字课程设计,还有诗词歌赋、经典名著等多样

微信小程序学习网站

小程序--柯神博客 http://www.cnblogs.com/nosqlcoco 案例地址: https://github.com/cocoli/weixin_smallexe/tree/master/weixin_demo/pages/component/uploadfile

探索Python的数学魔法:Numpy库的神秘力量

文章目录 探索Python的数学魔法:Numpy库的神秘力量背景:为什么选择Numpy?Numpy是什么?如何安装Numpy?五个简单的库函数使用方法场景应用常见Bug及解决方案总结 探索Python的数学魔法:Numpy库的神秘力量 背景:为什么选择Numpy? 在Python的世界中,数据处理和科学计算是不可或缺的一部分。但原生Python在处理大规模数据时可能会显