问题标题: 洛谷：P7447[Ynoi2007] rgxsxrs

Question

0

已解决

赵逸凡

初级启示者

我尝试用st表和树状数组强行动态维护数据（RMQ问题朴素解法），以达到部分分（过sub 3）和用于对拍分块/线段树正解。

#include<iostream>
#include<cstring>
using namespace std;
int n,m,a[500000],c[500000],st[200010][50],st2[200010][50],Log[200010];
inline int lowbit(int x)
{
	return x&(-x);
}
inline int sum(int x)
{
	int ret=0;
	while(x>0)
	{
		ret+=c[x];
		x-=lowbit(x);
	}
	return ret;
}
inline void add(int x,int v)
{
	while(x<=n)
	{
		c[x]+=v;
		x+=lowbit(x);
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		st[i][0]=a[i];
		st2[i][0]=a[i];
		add(i,a[i]);
	}
	for(int i=2;i<=n;i++)
		Log[i]=Log[i>>1]+1;
	for(int j=1;j<=20;j++)
		for(int i=1;i+(1<<j-1)-1<=n;i++)
			st[i][j]=max(st[i][j-1],st[i+(1<<j-1)][j-1]);
	//memset(st2,0x3f,sizeof(st2));	
	for(int j=1;j<=20;j++)
		for(int i=1;i+(1<<j-1)-1<=n;i++)
			st2[i][j]=min(st2[i][j-1],st2[i+(1<<j-1)][j-1]);		
	while(m--)
	{
		int opt,l,r;
		cin>>opt>>l>>r;
		if(opt==1)
		{
			int x;
			cin>>x;
			for(int j=l;j<=r;j++)
				if(a[j]>x)
					add(j,-x);
		}
		else
		{
			cout<<sum(r)-sum(l-1)<<"\n";
			//int p=Log[r-l+1];
			//cout<<min(st2[l][p],st2[r-(1<<p)+1][p])<<" ";
			//cout<<max(st[l][p],st[r-(1<<p)+1][p])<<"\n"; 
		}
	}
	return 0;
}
/*
for(int i=1;i<=n;i++)
	{
		scanf("%d",&a);
		st[i][0]=a;
	}
	scanf("%d",&m);
	Log[1]=0;
	for(int i=2;i<=n;i++)
		Log[i]=Log[i>>1]+1;
	for(int j=1;j<=20;j++)
		for(int i=1;i+(1<<j-1)-1<=n;i++)
			st[i][j]=max(st[i][j-1],st[i+(1<<j-1)][j-1]);	
	for(int i=1;i<=m;i++)
	{
		int l,r;
		scanf("%d%d",&l,&r);
		int p=Log[r-l+1];
		printf("%d\n",max(st[l][p],st[r-(1<<p)+1][p]));	
	}	
*/

具体的io读入，卡常细节以及算法的剪枝会在以后实现。

然后有些问题：

st表无法动态维护处理sub 2-sub 4

树状数组add出现异常，不是数据范围的原因

想不出来异或 lastans 该如何最优处理实现强制在线

求助如何解决。

赵逸凡在2021-03-21 11:04:27追加了内容

赵逸凡在2021-03-21 11:04:47追加了内容

赵逸凡在2021-03-21 14:52:15追加了内容

Answer 1

已采纳

王子桐

高级光能

@酷町侠

Answer 2

朱小川

缔造者

噗哈哈!!!

Answer 3

王子耀

缔造者

1

Answer 4

赵逸凡

初级启示者

@侯平仄 Div1的dalao /se

Answer 5

赵逸凡

初级启示者

update（3.21）：还有个问题，就是如何最优调过第一个操作（opt=1），我用的是st算法

目前只能过样例# 1的第一次询问，后面就无法动态了

#include<iostream>
#include<cstring>
using namespace std;
int n,m,a[500000],c[500000],st[200010][50],st2[200010][50],Log[200010];
inline int lowbit(int x)
{
    return x&(-x);
}
inline int sum(int x)
{
    int ret=0;
    while(x>0)
    {
        ret+=c[x];
        x-=lowbit(x);
    }
    return ret;
}
inline void add(int x,int v)
{
    while(x<=n)
    {
        c[x]+=v;
        x+=lowbit(x);
    }
}
inline void write(int x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
inline int read()
{
    int s=0,f=1;
    char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!=EOF){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        s=s*10+ch-'0';
        ch=getchar();
    }
    return s*f;
}
int main()
{
    n=read();
    m=read();
    for(int i=1;i<=n;i++)
    {
        a[i]=read();
        st[i][0]=a[i];
        st2[i][0]=a[i];
        add(i,a[i]);
    }
    for(int i=2;i<=n;i++)
        Log[i]=Log[i>>1]+1;
    for(int j=1;j<=20;j++)
        for(int i=1;i+(1<<j-1)-1<=n;i++)
            st[i][j]=max(st[i][j-1],st[i+(1<<j-1)][j-1]);
    memset(st2,0x3f,sizeof(st2));   
    for(int j=1;j<=20;j++)
        for(int i=1;i+(1<<j-1)-1<=n;i++)
            st2[i][j]=min(st2[i][j-1],st2[i+(1<<j-1)][j-1]);      
    while(m--)
    {
        int opt,l,r;
        opt=read();
        l=read();
        r=read();
        if(opt==1)
        {
            int x;
            x=read();
            for(int j=l;j<=r;j++)
                if(a[j]>x)
                {
                    add(j,-x);
                    st[j][0]=a[j]-x;
                    st2[j][0]=a[j]-x;
                    for(int k=1;k<=20;k++)
                        for(int i=1;i+(1<<k-1)-1<=n;i++)
                            st[i][k]=max(st[i][k-1],st[i+(1<<k-1)][k-1]); 
                    for(int k=1;k<=20;k++)
                        for(int i=1;i+(1<<k-1)-1<=n;i++)
                            st2[i][k]=min(st2[i][k-1],st2[i+(1<<k-1)][k-1]);
                }
        }
        else
        {
            write(sum(r)-sum(l-1));
            putchar(' ');
            int p=Log[r-l+1];
            write(min(st2[l][p],st2[r-(1<<p)+1][p]));
            putchar(' ');
            write(max(st[l][p],st[r-(1<<p)+1][p]));
            putchar('\n'); 
        }
    }
    return 0;
}
/*
for(int i=1;i<=n;i++)
    {
        scanf("%d",&a);
        st[i][0]=a;
    }
    scanf("%d",&m);
    Log[1]=0;
    for(int i=2;i<=n;i++)
        Log[i]=Log[i>>1]+1;
    for(int j=1;j<=20;j++)
        for(int i=1;i+(1<<j-1)-1<=n;i++)
            st[i][j]=max(st[i][j-1],st[i+(1<<j-1)][j-1]); 
    for(int i=1;i<=m;i++)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        int p=Log[r-l+1];
        printf("%d\n",max(st[l][p],st[r-(1<<p)+1][p]));   
    }   
*/

感觉是opt=1的操作的锅

Answer 6

赵逸凡

初级启示者

注意：这只是用于得到部分分（sub1-sub4）和对拍（就是自己造数据，然后利用这个程序写出结果，调试正解）

Answer 7

赵逸凡

初级启示者

@侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄 @侯平仄

快来看看啊

问题标题: 洛谷：P7447[Ynoi2007] rgxsxrs

7 个回答: