企业官网建设流程全解析

简洁的企业网站源码,网页设计免费模板参考网页,网站的域名每年都要续费,网站建设的几大原则区间取反与区间数一 时间限制#xff1a;2秒 空间限制#xff1a;256M 网页链接 牛客tracker 牛客tracker 每日一题#xff0c;完成每日打卡#xff0c;即可获得牛币。获得相应数量的牛币#xff0c;能在【牛币兑换中心】#xff0c;换取相应奖品#xff01;助…区间取反与区间数一时间限制2秒 空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述对于给定的长度为n nn的01 0101串s ss下标范围为[ 1 , n ] [1,n][1,n]你需要构建一个能够动态维护区间和信息的数据结构使得其能支持区间取反将[ l , r ] [l,r][l,r]这个区间中的全部元素进行取反操作即∀ i ∈ [ l , r ] , s i → 1 − s i ∀i∈[l,r],s_i→1−s_i∀i∈[l,r],si​→1−si​。区间数一输出下标在[ l , r ] [l,r][l,r]这个区间中的所有元素值为1 11的元素的个数即∑ i l r 1 ( a i 1 ) ∑_{il}^r1_{(a_i1)}∑ilr​1(ai​1)​。输入描述第一行输入两个整数n , q ( 1 ≦ n , q ≦ 5 × 10 5 ) n,q(1≦n,q≦5×10^5)n,q(1≦n,q≦5×105)代表01 0101串s ss的长度、操作次数。第二行输入一个长度为n nn的01 0101串s ( s i ∈ s(s_i∈s(si​∈{0 , 1 0,10,1}) ))此后q qq行每行先输入一个整数o p ( 1 ≦ o p ≦ 2 ) op(1≦op≦2)op(1≦op≦2)代表操作编号随后若o p 1 op1op1在同一行输入两个整数l , r ( 1 ≦ l ≦ r ≦ n ) l,r(1≦l≦r≦n)l,r(1≦l≦r≦n)代表区间取反若o p 2 op2op2在同一行输入两个整数l , r ( 1 ≦ l ≦ r ≦ n ) l,r(1≦l≦r≦n)l,r(1≦l≦r≦n)代表区间数一输出描述对于每一次询问输出一行一个整数代表区间数一的结果值。保证至少存在一次询问。示例1输入6 4 100101 1 1 4 2 1 6 1 4 6 2 1 6输出3解题思路采用位运算分块策略维护01 0101串将长度为n nn的01 0101串按每64 6464位划分为一个块用无符号长整型数组b s bsbs存储1 11对应位设为1 0 1010为0 00。处理区间取反o p 1 op1op1时先对[ l , r ) [l,r)[l,r)范围内的完整块整体按位取反异或− 1 -1−1再分别对左右边界的不完整块通过异或(1 u l l 1ull1ull(位偏移))− 1 -1−1取反边界内的位处理区间统计1 11的个数o p 2 op2op2时先计算右边界块前r位的1 11的数量减去左边界块前l ll位的1 11的数量再累加中间完整块的1 11的总数借助KaTeX parse error: Expected group after _ at position 1: _̲_builtin_popcou…快速统计每块1 11的个数。该方法将每次操作的时间复杂度降至O ( n / 64 ) O(n/64)O(n/64)适配n nn和q qq达5 e 5 5e55e5的规模高效完成区间取反与1 11的个数统计操作。代码内容#includebits/stdc.husingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefpairll,llpii;constll p1e97;constll N2e510;ull bs[7813];intmain(){ll n,q;string s;cinnqs;for(ll i0;in;i){if(s[i]1)bs[i6]|1ull(i63);}ll op,l,r,lb,rb;while(q--){cinoplr;l--;lbl6,rbr6;if(op1){for(ll ilb;irb;i)bs[i]^-1;bs[lb]^(1ull(l63))-1;bs[rb]^(1ull(r63))-1;continue;}ll res__builtin_popcountll(bs[rb](1ull(r63))-1)-__builtin_popcountll(bs[lb](1ull(l63))-1);for(ll ilb;irb;i)res__builtin_popcountll(bs[i]);coutresendl;}return0;}