被读入卡到哭了哪位大佬帮我看看读入哪有问题

P2801 教主的魔法

Parabola @ 2018-07-12 21:29:18

RT

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN=1000000+5;
int block[MAXN/1000+5][MAXN/1000+5];
int a[MAXN],wb[MAXN],wj[MAXN];
ll add[MAXN/1000+5];
int SIZE;
int n,m;
inline int read()
{
    char ch;int x=0;
    while(ch < '0' || ch >'9')  ch=getchar();
    while(ch >= '0' && ch <= '9')   x=x*10+ch-'0',ch=read();
    return x; 
}
inline void init()
{
    n=read();m=read();
    SIZE=sqrt(n);
    int j=0,b=0;
    for(int i=0;i<n;i++)
    {
        a[i]=read();
        block[b][j]=a[i];
        wb[i]=b;
        wj[i]=j;
        if(++j == SIZE)
            ++b,j=0;
    }
    for(int i=0;i<b;i++)
        sort(block[i],block[i]+SIZE);
    if(j != 0)
        sort(block[b],block[b]+j);
}
inline void change(int l,int r,int k)
{
    int lb=wb[l],rb=wb[r];
    if(lb == rb)
    {
        for(int i=l;i<=r;i++)
        {
            a[i]+=k;
            block[wb[i]][wj[i]]+=k;
        }
        sort(block[lb],block[rb]+SIZE);
    }
    else
    {
        for(int i=l;i < (lb+1) * SIZE;i++)
        {
            a[i]+=k;
            block[wb[i]][wj[i]]+=k;
        }
        for(int j=rb * SIZE;j <= r;j++)
        {
            a[j]+=k;
            block[wb[j]][wj[j]]+=k;
        }
        for(int i=lb+1;i<rb;i++)
            add[i]+=k;
    }
} 
inline char mygetchar()
{
    char ch=getchar();
    while(ch != 'A' && ch != 'M')   ch=getchar();
    return ch;
}
inline int query(int l,int r,int v)
{
    int tot=0;
    int lb=wb[l],rb=wb[r];
    if(lb == rb)
    {
        for(int i=l;i<=r;i++)
            if(a[i] >= v)
                tot++;
        return tot;
    }
    else
    {
        for(int i=l;i < (lb+1) * SIZE;i++)
            if(a[i]+add[wb[i]] >= v)
                tot++;
        for(int j=rb * SIZE;j <= r;j++)
            if(a[j]+add[wb[j]] >= v)    
                tot++;
        for(int i=lb+1;i<rb;i++)
            tot+=(SIZE-(lower_bound(block[i],block[i]+SIZE,v-add[i])-block[i]+1));
    }
    return tot;
}
int main()
{
    ios::sync_with_stdio(false);
    init();
    while(m--)
    {
        char opt=mygetchar();
        cout<<opt<<' ';
        if(opt == 'M')
            cout<<query(read(),read(),read())<<endl;
        else
            change(read(),read(),read());   
    }
    return 0;
}

by Eqvpkbz @ 2018-07-12 21:59:26

感觉此题有树状数组即视感


by scallop @ 2018-07-12 22:06:14

你的代码是有很大错误的。 具体来说,一个函数实参的求值顺序是不确定 的。


by 向noip冲刺 @ 2018-07-12 22:18:33

应该这样

inline int read()
{
    char ch = getchar();int x=0;
    while(ch < '0' || ch >'9')  ch=getchar();
    while(ch >= '0' && ch <= '9')   x=x*10+ch-'0',ch=read();
    return x; 
}

@白井黑子


by Dispwnl @ 2018-07-13 09:02:26

@白井黑子 您 ch=read();是什么操作啊,不应该是getchar()吗。。。难道是一种递归型的读入优化(逃


by Parabola @ 2018-07-13 11:18:15

打错了。。。

自己竟然没看到

我好蠢qwq


|