题目链接:Codeforces 400E Inna and Binary Logic
题目大意:给出n和m,表示有n个数,m次修改,然后给出n个数的值a1[i],通过a1数组可以推断出a2数组,长的为a1的长度减一,接着a3、a4直到an(长度为1),ai[k] = ai-1[k] & ai-1[k+1].sun为所有数的和。每次修改有p和x两个值,表示将a1数组的第p个位置修改成x,输出修改后的sum。
解题思路:假设一开始计算好了sun,然后每一次修改的时候,x和t[p],只要考虑二进制的每个位即可,如果(x&(1<<i)) == (t[p]&(1<<i))那么不变;如果(x&(1<<i)) = 1, (t[p]&(1<<i))=0,那么就要加上s;否则减掉s;s的计算方法:从p往左,连续的l个数t[j]&(1<<i) = 1,往右连续r个数t[j]&(1<<i) = 1,s = (l
+ r + l*r) * (1<<i)。因为如果出现有一个t[j]&(1<<i) = 0,那么在它后面有多少个t&(1<<i) = 1也没有用。解决完修改的部分,初始值计算就是个问题了,一开始用o(n^2)的方法超时了,很费解。初始值计算,对于每个位i,遍历一遍数组,计算各个连续的片t&(1<<i) = 1的个数c,s += (c*(c+1)*(1<<i)).
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long ll;
const int N = 1e5+5;
int n, m, t[N];
ll s;
void find(int k, ll& l, ll& r, int x) {
l = r = 0;
for (int i = x-1; i; i--) {
if ((t[i]&k) == 0) break;
l++;
}
for (int i = x+1; i <= n; i++) {
if ((t[i]&k) == 0) break;
r++;
}
}
void solve (int p, int x, int y) {
ll l, r;
for (int i = 0; (1<<i) < N; i++) {
int k = (1<<i);
if ((x&k) == (y&k)) continue;
find(k, l, r, p);
ll u = (l * r + l + r + 1) * (ll)k;
if (x&k) {
s += u;
} else {
s -= u;
}
}
}
void init () {
s = 0;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", &t[i]);
for (int i = 0; (1<<i) < N; i++) {
int k = (1<<i);
ll c = 0;
for (int j = 1; j <= n; j++) {
if (t[j]&k) c++;
else {
if (c) s += (c*(c+1)*(ll)k/2);
c = 0;
}
}
if (c) s += (c*(c+1)*(ll)k/2);
}
}
int main () {
init ();
int p, x;
for (int i = 0; i < m; i++) {
scanf("%d %d", &p, &x);
solve (p, x, t[p]);
t[p] = x;
cout << s << endl;
}
return 0;
}
分享到:
相关推荐
codeforces 19 E Fairy 一道比较难的题目的解题报告 推荐阅读
暴枚最长桌脚的长度$l$,然后长度比$l$长的桌脚全部都要砍掉长度比$l$短的桌脚选择代价前$k$小的砍掉用线段树维护;示例程序 :typedef long l
Codeforces 题库 101-200 共~500题 codeforces.com版权所有。 程序可提交至该网站评测。
Codeforces 题库 001-100 共~500题 codeforces.com版权所有。 程序可提交至该网站评测。
codeforces编程网站预测分数插件
使用于Google Chrome的Codeforces Enhancer 1.1.2插件安装包。 版本:codeforces enhancer 1.1.2 使用浏览器:Google Chrome
binarysearch-codeforces
Codeforces 1105B - Zuhair and Strings 测试点37个(全)
Codeforces 185A - Plant 全测试点49个
codeforces每日一题。 题意: 给出一个数组,让你挑选出能组成任意pair差值为2的幂的序列,并且使这个序列长度尽可能大。 思路: 针对于挑选出来的序列,任意pair对的差值为2的幂数。 假设有多个pair对,设dis(a,b)=2...
Codeforces global round 10 codes
E. Array Shrinking time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard output You are given an array a1,a2,…,an. You can perform the following operation...
Codeforces round 678 division 2 codes
Some of the Codeforces problems codes
题目大意:给出 n 个数字组成的序列,现在可以对数列进行多次操作,每次操作可以选择其中一段连续的数列,用其平均数替换原位置,换句话说,若原连续数列为 1 2 3,则可以替换为 2 2 2,问如何操作可以使得最后答案...
Codeforces扩展包 是否曾经想让Codeforce拥有方便的快捷键,自动更新排行榜,可以按需隐藏/显示的问题标签,更好的站点导航,深色主题或以上所有功能? 这些和更多功能可以在Codeforces ++中获得! 该扩展是开源的,...
Codeforces round 678 D2_Codeforces_源码
CodeForces :bar_chart: 使用Java
打codeforces的神器
一个Codeforces、牛客竞赛、AtCoder平台的编程竞赛查询插件,ACMer必备.zip