hdoj4391 Paint The Wall

2015年12月15日 0 作者 CrazyKK

http://acm.hdu.edu.cn/showproblem.php?pid=4391
题意：有 n 个点，每个点有一种颜色（可能相同），两种操作：1、将区间 [a,b] 染成颜色 c ; 2、询问区间 [a,b] 中颜色为 c 的点有多少个。
思路：因为颜色种类很多。。。没办法通过建很多棵线段树解决。我们用分块的办法。。。




/* ***********************************************
Author :111qqz
Created Time :2015年12月15日 星期二 15时00分34秒
File Name :code/hdoj/4391.cpp
************************************************ */

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair

using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=1E5+7; //sqrt(n),n最大100000
int n,q,c[N];
int len ,cnt;
struct HashBlock{
    int  siz; //块的大小，因为最后一个快的长度可能不足len,
    int col;//整块的颜色。当快没有被标记成统一的颜色的时候，为-1
    map<int,int>mp;
}a[400];

void init()
{
    len = (int)sqrt(n*1.0);
    cnt = (n-1)/len+1;
    for ( int i = 0 ; i < cnt ; i++)
    {
	a[i].siz = min(n,(i+1)*len)-i*len;
	a[i].col = -1;
	a[i].mp.clear();
    }

    for ( int i = 0 ; i < n ; i++)
    {
	scanf("%d",&c[i]);
	a[i/len] .mp[c[i]]++;
    }
}

void Push_Down( int step)
{
    if (a[step].col!=-1)
    {
	a[step].mp.clear();
	for ( int i = step*len ; i<min((step+1)*len,n); i++)
	{
	    c[i] = a[step].col;
	    a[step].mp[c[i]]++;
	}
	a[step].col = -1;
    }
}

void update(int l,int r,int col)
{
    int la=l/len,ra=r/len;
    for(int i=la+1;i<ra;i++) a[i].col=col;
    if(la!=ra)
    {
        Push_Down(la);Push_Down(ra);
        for(int i=l;i<len*(1+la);i++)
        {
            a[la].mp[c[i]]--;a[la].mp[col]++;c[i]=col;
        }
        for(int i=ra*len;i<=r;i++)
        {
            a[ra].mp[c[i]]--;a[ra].mp[col]++;c[i]=col;
        }
    }
    else
    {
        Push_Down(la);
        for(int i=l;i<=r;i++)
        {
            a[la].mp[c[i]]--;a[la].mp[col]++;c[i]=col;
        }
    }
}
int query(int l,int r,int col)
{
    int la = l/len;
    int ra = r/len;
    int ans = 0 ;
    for ( int i = la+1 ; i < ra ; i++)
    {
	if (a[i].col==col) ans +=a[i].siz;
	    else if(a[i].col==-1&&a[i].mp.find(col)!=a[i].mp.end()) ans+=a[i].mp[col];
    }
    if (la!=ra)   //首尾两段暴力查询...
    {
	Push_Down(la);
	Push_Down(ra);
	for ( int i = l ; i < len*(la+1);  i++)
	{
	    ans+=col==c[i];
	    //if (c[i]==col) ans++;
	}
	for ( int i = ra*len ; i <= r ; i++)
	{
	    ans+=col==c[i];
	}


    }
    else
    {
	Push_Down (la);
	for ( int i = l ; i <= r ; i++)
	{
	    ans+=col==c[i];
	    //if (c[i]==col) ans++;
	}
    }
    return ans;
}
int main()
{
	#ifndef  ONLINE_JUDGE 
	freopen("code/in.txt","r",stdin);
  #endif

	while (scanf("%d%d",&n,&q)!=EOF)
	{
	    init();
	    while (q--)
	    {
		int k,l,r,c;
		scanf("%d%d%d%d",&k,&l,&r,&c);
		if (k==1) update(l,r,c);
		else printf("%d\n",query(l,r,c));
	    }
	}

  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

/* ***********************************************

Author :111qqz

Created Time :2015年12月15日星期二 15时00分34秒

File Name :code/hdoj/4391.cpp

************************************************ */

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <cmath>

#include <cstdlib>

#include <ctime>

#define fst first

#define sec second

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define ms(a,x) memset(a,x,sizeof(a))

typedef long long LL;

#define pi pair < int ,int >

#define MP make_pair

using namespace std;

const double eps = 1E-8;

const int dx4[4]={1,0,0,-1};

const int dy4[4]={0,-1,1,0};

const int inf = 0x3f3f3f3f;

const int N=1E5+7; //sqrt(n),n最大100000

int n,q,c[N];

int len ,cnt;

struct HashBlock{

int siz; //块的大小，因为最后一个快的长度可能不足len,

int col;//整块的颜色。当快没有被标记成统一的颜色的时候，为-1

map<int,int>mp;

}a[400];

void init()

{

len = (int)sqrt(n*1.0);

cnt = (n-1)/len+1;

for ( int i = 0 ; i < cnt ; i++)

{

a[i].siz = min(n,(i+1)*len)-i*len;

a[i].col = -1;

a[i].mp.clear();

}

for ( int i = 0 ; i < n ; i++)

{

scanf("%d",&c[i]);

a[i/len] .mp[c[i]]++;

}

void Push_Down( int step)

{

if (a[step].col!=-1)

{

a[step].mp.clear();

for ( int i = step*len ; i<min((step+1)*len,n); i++)

{

c[i] = a[step].col;

a[step].mp[c[i]]++;

}

a[step].col = -1;

}

void update(int l,int r,int col)

{

int la=l/len,ra=r/len;

for(int i=la+1;i<ra;i++) a[i].col=col;

if(la!=ra)

{

Push_Down(la);Push_Down(ra);

for(int i=l;i<len*(1+la);i++)

{

a[la].mp[c[i]]--;a[la].mp[col]++;c[i]=col;

}

for(int i=ra*len;i<=r;i++)

{

a[ra].mp[c[i]]--;a[ra].mp[col]++;c[i]=col;

}

else

{

Push_Down(la);

for(int i=l;i<=r;i++)

{

a[la].mp[c[i]]--;a[la].mp[col]++;c[i]=col;

}

int query(int l,int r,int col)

{

int la = l/len;

int ra = r/len;

int ans = 0 ;

for ( int i = la+1 ; i < ra ; i++)

{

if (a[i].col==col) ans +=a[i].siz;

else if(a[i].col==-1&&a[i].mp.find(col)!=a[i].mp.end()) ans+=a[i].mp[col];

}

if (la!=ra) //首尾两段暴力查询...

{

Push_Down(la);

Push_Down(ra);

for ( int i = l ; i < len*(la+1); i++)

{

ans+=col==c[i];

//if (c[i]==col) ans++;

}

for ( int i = ra*len ; i <= r ; i++)

{

ans+=col==c[i];

}

else

{

Push_Down (la);

for ( int i = l ; i <= r ; i++)

{

ans+=col==c[i];

//if (c[i]==col) ans++;

}

return ans;

}

int main()

{

#ifndef ONLINE_JUDGE

freopen("code/in.txt","r",stdin);

#endif

while (scanf("%d%d",&n,&q)!=EOF)

{

init();

while (q--)

{

int k,l,r,c;

scanf("%d%d%d%d",&k,&l,&r,&c);

if (k==1) update(l,r,c);

else printf("%d\n",query(l,r,c));

}

#ifndef ONLINE_JUDGE

fclose(stdin);

#endif

return 0;

}

分类目录hdoj

标签hash stl 分块

关于作者

CrazyKK

ex-ACMer@hust，stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人！