HDU4391 Paint The Wall - c++编程基础

2012 Multi-University Training Contest 10
1002题
将区间分为sqrt(n)段，统计每一段每种颜色的数量，利用Lazy的思想维护。

[cpp]
#include
#include
#include
#include
#include
using namespace std;
const int MAXN = 100005;
const int MAXM = 1005;
const double eps = 1e-8;

int n, m;
int color[MAXN];
int segNum, segSize;

struct Segment
{
int sameColor;
map colorNum;
}segment[MAXM];

void hash(int index)
{
segment[index].sameColor = -1;
segment[index].colorNum.clear();
int start = index * segSize;
for(int i=0;i {
++ segment[index].colorNum[color[i+start]];
}
}

void init()
{
segSize = (int) sqrt(n + eps);
segNum = n / segSize;
if(n % segSize)
{
++ segNum;
}
for(int i=0;i {
hash(i);
}
}

void relax(int index)
{
if(segment[index].sameColor != -1)
{
int start = index * segSize;
int cnt = 0;
for(int i=0;i {
color[i + start] = segment[index].sameColor;
++ cnt;
}
segment[index].colorNum.clear();
segment[index].colorNum[segment[index].sameColor] = cnt;
segment[index].sameColor = -1;
}
}

void update(int l, int r, int c)
{
int indexL = l / segSize;
int indexR = r / segSize;
if(indexL == indexR)
{
relax(indexL);
for(int i=l;i<=r;++i)
{
color[i] = c;
}
hash(indexL);
}
else
{
relax(indexL);
relax(indexR);
int endL = (indexL + 1) * segSize;
for(int i=l;i {
color[i] = c;
}
hash(indexL);
int startR = indexR * segSize;

for(int i=startR;i<=r;++i)
{
color[i] = c;
}
hash(indexR);
for(int i=indexL+1;i {
segment[i].sameColor = c;
}
}
}

int query(int l, int r, int c)
{
int indexL = l / segSize;
int indexR = r / segSize;
int ret = 0;
if(indexL == indexR)
{
relax(indexL);
for(int i=l;i<=r;++i)
{
if(color[i] == c)
{
++ ret;
}
}
}
else
{
relax(indexL);
relax(indexR);
int endL = (indexL + 1) * segSize;
for(int i=l;i {
if(color[i] == c)
{
++ ret;
}
}
int startR = indexR * segSize;
for(int i=startR;i<=r;++i)
{
if(color[i] == c)
{
++ ret;
}
}
for(int i=indexL+1;i {
if(segment[i].sameColor == -1)
{
if(segment[i].colorNum.find(c) != segment[i].colorNum.end())
{
ret += segment[i].colorNum[c];
}
}
else
{
if(segment[i].sameColor == c)
{
ret += segSize;
}
}
}
}
return ret;
}

int main()
{
int a, l, r, c;
while(~scanf("%d%d", &n, &m))
{
for(int i=0;i {
scanf("%d", &color[i]);
}
init();
while(m--)
{
scanf("%d%d%d%d", &a, &l, &r, &c);
if(a == 1)
{
update(l, r, c);
}
else
{

HDU4391 Paint The Wall(一)