加载中…HDU 3854 Glorious Array 北邮邀请赛
(2011-07-18 19:29:35)
标签：
hdu3854gloriousarray北邮邀请赛it |
分类： 杂题 |
题目描述：
给你n个数，和每个数字的状态（0或者1）。
有两种操作：
第一种：翻转某个数字的状态。
第二种：询问，要求输入满足条件的i， j组合个数。
一个满足条件的i，j要求：
A：1 <= i <= j <= n
B: i和j数字的状态不同
C：i和j的闭区间内的数字的最小值小于k（k由输入给定）
解题报告：
对于一开始的输入先求出组合个数。
然后对于每次的翻转状态，更新组合个数：
比如翻转i，如果x[i] < k, 那么只需看i左侧有多少个0或者1（具体看x[i]当前状态），和i右侧有多少个0或者1（同上），就可以知道这次翻转具体变化了多少，具体的实现可以用树状数组。
如果x[i] > k，初始化时记下在i左侧最近的小于k的数字的位置L[i]，同理R[i]。
找到L[i]左侧0或者1的个数和R[i]右侧0或者1的个数，就是这次变化的个数。
应该比较好理解。
代码如下：
typev s
= 0;
for ( ;
i > 0; s += ar[i], i -= lowb(i));
return
s;
memset(L, -1, sizeof(L)); memset(R, -1,
sizeof(R));
memset(ar, 0, sizeof(ar));
for(int
i = 1; i <= n; i++) if (x[i] <
k)
for(int j = i + 1; j
<= n && x[j]
>= k; j++)
L[j] = i;
for(int
i = n; i >= 1; i--) if (x[i] <
k)
for(int j = i - 1; j
>= 1 && x[j]
>= k; j--)
R[j] = i;
//printf("l %d r %d %d %d\n", l, r, sum(r), sum(l
- 1));
if (l
> r) return 0;
if (l
== -1 || r == -1) return 0;
if (now
== 0) return r - l + 1 - (sum(r) - sum(l - 1));
return
sum(r) - sum(l - 1);
int
t;scanf("%d", &t);
while(t--)
{
scanf("%d%d%d",
&n, &m, &k);
for(int i = 1; i
<= n; i++) scanf("%d", &x[i]);
init();
for(int i = 1; i
<= n; i++)
{
scanf("%d", &sta[i]);
if (sta[i]) add(i, 1);
}
nowans = 0;
for(int i = 1; i
<= n; i++)
if (x[i] < k) nowans += Get(i + 1,
n, !sta[i]);
else nowans += Get(R[i], n, !sta[i]);
//cout
<< nowans
<< endl;
while(m--)
{
int tmp;scanf("%d", &tmp);
if (tmp == 1) cout
<< nowans
<< endl;
else
{
scanf("%d",
&tmp);
int before
= 0, after = 0;
int i =
tmp;
if (x[tmp]
< k)
{
before += Get(1, i - 1,
!sta[i]) + Get(i + 1, n, !sta[i]);
after += Get(1, i - 1, sta[i])
+ Get(i + 1, n, sta[i]);
}else
{
before += Get(1, L[i],
!sta[i]) + Get(R[i], n, !sta[i]);
after += Get(1, L[i], sta[i])
+ Get(R[i], n, sta[i]);
}
if (sta[i]
== 0) add(i, 1), sta[i] = 1;
else add(i,
-1), sta[i] = 0;
nowans +=
(after - before);
}
}
}
return
0;
给你n个数，和每个数字的状态（0或者1）。
有两种操作：
第一种：翻转某个数字的状态。
第二种：询问，要求输入满足条件的i， j组合个数。
一个满足条件的i，j要求：
A：1 <= i <= j <= n
B: i和j数字的状态不同
C：i和j的闭区间内的数字的最小值小于k（k由输入给定）
解题报告：
对于一开始的输入先求出组合个数。
然后对于每次的翻转状态，更新组合个数：
比如翻转i，如果x[i] < k, 那么只需看i左侧有多少个0或者1（具体看x[i]当前状态），和i右侧有多少个0或者1（同上），就可以知道这次翻转具体变化了多少，具体的实现可以用树状数组。
如果x[i] > k，初始化时记下在i左侧最近的小于k的数字的位置L[i]，同理R[i]。
找到L[i]左侧0或者1的个数和R[i]右侧0或者1的个数，就是这次变化的个数。
应该比较好理解。
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define typev int // type of res
#define N 200000
typev ar[N]; // index: 1 ~ N
int lowb(int t) { return t & (-t) ; }
void add(int i, typev v)
{for ( ; i < N; ar[i] += v, i +=
lowb(i));}
typev sum(int i)
{
}
int n, m, k;
long long nowans;
int x[N], L[N], R[N], sta[N];
void init()
{
}
int Get(int l, int r, int now)
{
}
int main()
{
}
喜欢
0
赠金笔