1
22
2016
0

【bzoj2724】【Violet 6】蒲公英

2724: [Violet 6]蒲公英

Time Limit: 40 Sec  Memory Limit: 512 MB
Submit: 1182  Solved: 389
[Submit][Status][Discuss]

Description

 

Input

修正一下

l = (l_0 + x - 1) mod n + 1, r = (r_0 + x - 1) mod n + 1

Output

Sample Input

6 3
1 2 3 2 1 2
1 5
3 6
1 5

Sample Output

1
2
1

HINT

 


修正下：


n <= 40000, m <= 50000

 

Source

Vani原创

大家可以先看一下陈立杰的论文《区间众数解题报告》，这道题是没有修改的情况。我们只要用分块大法做就可以了。

附：陈立杰论文截取

代码：

 

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
int n,q,m,x,y,ans,Max,L,R,len,num;
int a[40010],p[40010],b[40010],c[40010],le[40010],ri[40010],sum[40010];
int l[210],r[210],f[210][210],g[210][210];
int get(int l,int r,int x)
{return upper_bound(c+le[x],c+ri[x]+1,r)-lower_bound(c+le[x],c+ri[x]+1,l);}
void ask(int l,int r,int x,int y)
{
	for (int i=x;i<=y;i++)
	{
		int cnt=get(l,r,a[i]);
		if (cnt>Max||(cnt==Max&&a[i]<ans)){ans=a[i];Max=cnt;}
	}
}
int main()
{
	scanf("%d%d",&n,&q);
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		p[i]=a[i];
	}
	m=n;
	sort(p+1,p+m+1);
	m=unique(p+1,p+m+1)-p-1;
	for (int i=1;i<=n;i++)
		a[i]=lower_bound(p+1,p+m+1,a[i])-p;
	for (int i=1;i<=n;i++)
		b[a[i]]++;
	for (int i=1;i<=m;i++)
		b[i]+=b[i-1];
	for (int i=1;i<=m;i++){le[i]=b[i-1]+1;ri[i]=b[i-1];}
	for (int i=1;i<=n;i++) c[++ri[a[i]]]=i;
	len=(int)sqrt(n);
	num=n/len;if (n%len) num++;
	for (int i=1;i<=num;i++){l[i]=(i-1)*len+1;r[i]=min(i*len,n);}
	for (int i=1;i<=num;i++)
	{
		x=y=0;
		memset(sum,0,sizeof(sum));
		for (int j=i;j<=num;j++)
		{
			for (int k=l[j];k<=r[j];k++)
			{
				sum[a[k]]++;
				if (sum[a[k]]>y||(sum[a[k]]==y&&a[k]<x)){x=a[k];y=sum[a[k]];}
			}
			f[i][j]=x;g[i][j]=y;
		}
	}
	ans=0;
	while (q--)
	{
		scanf("%d%d",&x,&y);
		x=(x+ans-1)%n+1;y=(y+ans-1)%n+1;
		if (x>y) swap(x,y);
		L=x/len;if (r[L]<x) L++;
		R=y/len;if (r[R]<y) R++;
		ans=0;Max=0;
		if (L==R) {ask(x,y,x,y);ans=p[ans];printf("%d\n",ans);continue;}
		if (R-1>=L+1){ans=f[L+1][R-1];Max=g[L+1][R-1];}
		ask(x,y,x,r[L]);ask(x,y,l[R],y);
		ans=p[ans];
		printf("%d\n",ans);
	}
}
Category: 分块 | Tags:
1
22
2016
0

【bzoj2453】维护队列

2453: 维护队列

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 521  Solved: 222
[Submit][Status][Discuss]

Description

你小时候玩过弹珠吗？
小朋友A有一些弹珠，A喜欢把它们排成队列，从左到右编号为1到N。为了整个队列鲜艳美观，小朋友想知道某一段连续弹珠中，不同颜色的弹珠有多少。当然，A有时候会依据个人喜好，替换队列中某个弹珠的颜色。但是A还没有学过编程，且觉得头脑风暴太浪费脑力了，所以向你来寻求帮助。

Input

输入文件第一行包含两个整数N和M。
第二行N个整数，表示初始队列中弹珠的颜色。
接下来M行，每行的形式为“Q L R”或“R x c”，“Q L R”表示A想知道从队列第L个弹珠到第R个弹珠中，一共有多少不同颜色的弹珠，“R x c”表示A把x位置上的弹珠换成了c颜色。

Output

对于每个Q操作，输出一行表示询问结果。

Sample Input

2 3
1 2
Q 1 2
R 1 2
Q 1 2

Sample Output

2
1

HINT

 

对于100%的数据，有1 ≤ N ≤ 10000, 1 ≤ M ≤ 10000，小朋友A不会修改超过1000次，所有颜色均用1到10^6的整数表示。

Source

2011福建集训

我们首先定义一个pre数组，pre[i]表示i之前与i颜色相同的最近的点编号。

那么对于询问（x,y）只要计算x~y的pre中小于x的个数，就是答案。至于计算，我们可以分块来解决。

对于修改，直接暴力修改，能水过的。

代码：

 

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m,len,num,L,R,ans,x,y;
char opt[10];
int a[10010],b[10010],pre[10010],last[1000010],l[110],r[110],flag[110];
int ask(int l,int r)
{
    int ans=0;
    for (int i=l;i<=r;i++) if (b[i]<x) ans++;
    return ans;
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for (int i=1;i<=n;i++)
    {
        pre[i]=b[i]=last[a[i]];
        last[a[i]]=i;
    }
    len=(int)sqrt(n);
    if (n%len==0) num=n/len;else num=n/len+1;
    for (int i=1;i<=num;i++)
    {
        l[i]=(i-1)*len+1;r[i]=min(i*len,n);
        sort(pre+l[i],pre+r[i]+1);
    }
    while (m--)
    {
        scanf("%s%d%d",&opt,&x,&y);
        if (opt[0]=='Q')
        {
            L=x/len;
            if (x>r[L]) L++;
            R=y/len;
            if (y>r[R]) R++;
            if (L==R){printf("%d\n",ask(x,y));continue;}
            ans=ask(x,r[L])+ask(l[R],y);
            for (int i=L+1;i<R;i++)
                ans+=lower_bound(pre+l[i],pre+r[i]+1,x)-pre-l[i];
            printf("%d\n",ans);
        }else
        {
            for (int i=1;i<=n;i++) last[a[i]]=0;
            a[x]=y;
            for (int i=1;i<=num;i++) flag[i]=0;
            for (int i=1;i<=n;i++)
            {
                if (b[i]!=last[a[i]]) flag[(i-1)/len+1]=1;
                b[i]=last[a[i]];
                last[a[i]]=i;
            }
            for (int i=1;i<=num;i++)
            if (flag[i])
            {
                for (int j=l[i];j<=r[i];j++)
                    pre[j]=b[j];
                sort(pre+l[i],pre+r[i]+1);
            }
        }
    }
}
Category: 分块 | Tags:
12
28
2015
0

【bzoj3343】教主的魔法

3343: 教主的魔法

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 696  Solved: 300
[Submit][Status][Discuss]

Description

教主最近学会了一种神奇的魔法，能够使人长高。于是他准备演示给XMYZ信息组每个英雄看。于是N个英雄们又一次聚集在了一起，这次他们排成了一列，被编号为1、2、……、N。
每个人的身高一开始都是不超过1000的正整数。教主的魔法每次可以把闭区间[L, R]（1≤L≤R≤N）内的英雄的身高全部加上一个整数W。（虽然L=R时并不符合区间的书写规范，但我们可以认为是单独增加第L（R）个英雄的身高）
CYZ、光哥和ZJQ等人不信教主的邪，于是他们有时候会问WD闭区间 [L, R] 内有多少英雄身高大于等于C，以验证教主的魔法是否真的有效。
WD巨懒，于是他把这个回答的任务交给了你。
 

Input

       第1行为两个整数N、Q。Q为问题数与教主的施法数总和。
       第2行有N个正整数，第i个数代表第i个英雄的身高。
       第3到第Q+2行每行有一个操作：
（1）       若第一个字母为“M”，则紧接着有三个数字L、R、W。表示对闭区间 [L, R] 内所有英雄的身高加上W。
（2）       若第一个字母为“A”，则紧接着有三个数字L、R、C。询问闭区间 [L, R] 内有多少英雄的身高大于等于C。
 

Output

       对每个“A”询问输出一行，仅含一个整数，表示闭区间 [L, R] 内身高大于等于C的英雄数。
 

Sample Input

5 3
1 2 3 4 5
A 1 5 4
M 3 5 1
A 1 5 4

Sample Output

2
3

HINT

【输入输出样例说明】

原先5个英雄身高为1、2、3、4、5，此时[1, 5]间有2个英雄的身高大于等于4。教主施法后变为1、2、4、5、6，此时[1, 5]间有3个英雄的身高大于等于4。

 

【数据范围】

对30%的数据，N≤1000，Q≤1000。
对100%的数据，N≤1000000，Q≤3000，1≤W≤1000，1≤C≤1,000,000,000。
 

刷道水。。

直接分块就好了。

代码：

 

#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
int n,m,len,num,ans,x,y,l,r;
int L[1010],R[1010];
ll tag[1010],val;
char ch[5];
struct node{ll x;int loc;}a[1000010];
bool cmp(const node x,const node y){return x.x<y.x;}
int ask(int k,int l,int r,ll x)
{
    int ans=0;
    for (int i=L[k];i<=R[k];i++)
    if (a[i].loc>=l&&a[i].loc<=r&&a[i].x>=x) ans++;
    return ans; 
}
void add(int k,int l,int r,ll x)
{
    for (int i=L[k];i<=R[k];i++)
    if (a[i].loc>=l&&a[i].loc<=r) a[i].x+=x;
}
int binary(int l,int r,ll x)
{
    if (l==r){if (a[l].x<x) return l+1;else return l;}
    int mid=(l+r)>>1;
    if (a[mid].x>=x) return binary(l,mid,x);else return binary(mid+1,r,x);
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++){scanf("%lld",&a[i].x);a[i].loc=i;}
    len=(int)sqrt(n);
    if (n%len==0) num=n/len;else num=n/len+1;
    for (int i=1;i<=num;i++)
    {
        L[i]=(i-1)*len+1;
        R[i]=min(n,i*len);
        sort(a+L[i],a+R[i]+1,cmp);
    }
    while (m--)
    {
        scanf("%s",ch);
        if (ch[0]=='A')
        {
            scanf("%d%d%lld",&x,&y,&val);
            l=x/len;if (R[l]<x) l++;
            r=y/len;if (R[r]<y) r++;
            ans=0;
            if (l==r){ans+=ask(l,x,y,val);printf("%d\n",ans);continue;}
            ans+=ask(l,x,R[l],val);
            ans+=ask(r,L[r],y,val);
            for (int i=l+1;i<r;i++)
                ans+=R[i]-binary(L[i],R[i],val-tag[i])+1;
            printf("%d\n",ans);
        }else
        {
            scanf("%d%d%lld",&x,&y,&val);
            l=x/len;if (R[l]<x) l++;
            r=y/len;if (R[r]<y) r++;
            if (l==r){add(l,x,y,val);continue;}
            add(l,x,R[l],val);
            add(r,L[r],y,val);
            for (int i=l+1;i<r;i++)
                tag[i]+=val;
        }
    }
}

Category: 分块 | Tags:
12
22
2015
0

【JSOI2015】最佳南瓜

易知，每次操作后中位数要么不变要么增加一。因此我们只要分块判断此时的中位数是否需要加一。

代码：

 

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m,mid,x,y,L,R,len,num,sum,k;
int l[10010],r[10010],b[100010],tag[10010];
struct node{int x,id;}a[100010];
bool cmp(const node x,const node y){return x.x<y.x;}
void add(int x,int L,int R)
{
    for (int i=l[x];i<=r[x];i++)if (a[i].id>=L&&a[i].id<=R)a[i].x++;
    sort(a+l[x],a+r[x]+1,cmp);
}
int binary(int l,int r,int x)
{
    if (l==r) return l;
    int mid=(l+r)>>1;
    if (a[mid].x>=x) return binary(l,mid,x);return binary(mid+1,r,x);
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&a[i].x);
        a[i].id=i;
    }
    for (int i=1;i<=n;i++)
        b[i]=a[i].x;
    nth_element(b+1,b+(n/2)+1,b+n+1);
    mid=b[n/2+1];
    len=(int)sqrt(n);
    if (n%len) num=n/len+1;else num=n/len;
    for (int i=1;i<=num;i++)
    {
        l[i]=(i-1)*len+1;
        r[i]=min(n,i*len);
        sort(a+l[i],a+r[i]+1,cmp);
    }
    for (int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        L=x/len;
        if (x>r[L]) L++;
        R=y/len;
        if (y>r[R]) R++;
        if (L==R) add(L,x,y);else
        {   
            add(L,x,r[L]);add(R,l[R],y);
            for (int j=L+1;j<R;j++) tag[j]++;
        }
        sum=0;
        mid++;
        for (int j=1;j<=num;j++)
        {
            k=binary(l[j],r[j],mid-tag[j]);
            if (a[k].x>=mid-tag[j]) k--;
            if (k>=l[j]) sum+=k-l[j]+1;
        }
        if (sum>n/2) mid--;
        printf("%d\n",mid);
    }
}
Category: 分块 | Tags:

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com