求助,几乎全WA

P1527 [国家集训队] 矩阵乘法

xiaolilsq @ 2020-02-11 17:40:24

评测情况

程序:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
template<typename T>void read(T &x){
    x=0;int f(1);char c(getchar());
    for(;!isdigit(c);c=getchar())if(c=='-')f=-f;
    for(; isdigit(c);c=getchar())x=(x<<3)+(x<<1)+(c-'0');
    x*=f;
}
template<typename T>void write(T x){
    if(x<0)putchar('-'),x=-x;
    if(x/10)write(x/10),x%=10;
    putchar(x+'0');
}
const int maxn=707,maxq=100006;
int n;
struct tree{
    int a[maxn][maxn];
    int lowbit(int x){
        return x&-x;
    }
    void add(int l,int r,int v){
        for(int x=l;x<=n;x+=lowbit(x))
            for(int y=r;y<=n;y+=lowbit(y))
                a[x][y]+=v;
    }
    int query(int l,int r){
        int ans=0;
        for(int x=l;x;x-=lowbit(x))
            for(int y=r;y;y-=lowbit(y))
                ans+=a[x][y];
        return ans;
    }
}T;
long long va[maxn*maxn];
struct _1{
    int X,Y,val;
}_1_[maxn*maxn],_11[maxn*maxn],_12[maxn*maxn];
struct _2{
    int X1,X2,Y1,Y2,k,num;
}_2_[maxq],_21[maxq],_22[maxq];
int ans[maxq];
void solve(int tl,int tr,int l,int r,int L,int R){
    if(L>R)return;
    if(tl==tr){
        for(int i=L;i<=R;++i){
            ans[_2_[i].num]=va[tl];
        }
        return;
    }
    int mid=tl+tr>>1,_11cn=0,_12cn=0,_21cn=0,_22cn=0;
    for(int i=l;i<=r;++i){
        if(_1_[i].val<=mid){
            T.add(_1_[i].X,_1_[i].Y,1);
            _11[_11cn++]=_1_[i];
        }
        else{
            _12[_12cn++]=_1_[i];
        }
    }
    for(int i=L;i<=R;++i){
        int k=T.query(_2_[i].X2,_2_[i].Y2)+T.query(_2_[i].X1-1,_2_[i].Y1-1)
             -T.query(_2_[i].X1-1,_2_[i].Y2)-T.query(_2_[i].X2,_2_[i].Y1-1);
        if(_2_[i].k<=k){
            _21[_21cn++]=_2_[i];
        }
        else{
            _2_[i].k-=k;
            _22[_22cn++]=_2_[i];
        }
    }
    for(int i=0;i<_11cn;++i)
        T.add(_11[i].X,_11[i].Y,-1);
    for(int i=0;i<_11cn;++i)_1_[l+i]=_11[i];
    for(int i=0;i<_12cn;++i)_1_[l+_11cn+i]=_12[i];
    for(int i=0;i<_21cn;++i)_2_[L+i]=_21[i];
    for(int i=0;i<_22cn;++i)_2_[L+_21cn+i]=_22[i];
    solve(tl,mid,l,l+_11cn-1,L,L+_21cn-1);
    solve(mid+1,tr,l+_11cn,r,L+_21cn,R);
}
int main(){
    read(n);int q,cnt=0,vc=0;read(q);
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            _1_[cnt].X=i;_1_[cnt].Y=j;
            read(_1_[cnt].val);
            va[vc++]=_1_[cnt].val;
            ++cnt;
        }
    }
    sort(va,va+vc);vc=unique(va,va+vc)-va;
    for(int i=1;i<=n*n;++i)
        _1_[i].val=lower_bound(va,va+vc,_1_[i].val)-va;
    for(int i=0;i<q;++i){
        read(_2_[i].X1);
        read(_2_[i].Y1);
        read(_2_[i].X2);
        read(_2_[i].Y2);
        read(_2_[i].k);
        _2_[i].num=i;
    }
    solve(0,vc-1,0,cnt-1,0,q-1);
    for(int i=0;i<q;++i)write(ans[i]),putchar('\n');
    return 0;
}

求各位大佬帮忙查错,感谢


by 春日野悠 @ 2020-02-11 17:43:49

%%%


by xiaolilsq @ 2020-02-11 17:47:09

查了好久了,就是找不到问题


by xiaolilsq @ 2020-04-23 14:12:37

找到错误了。


by Develop @ 2020-05-05 22:15:43

%%%%


|