QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#659979#7007. Rikka with Data Structurespengpeng_fudanWA 3304ms22544kbC++236.0kb2024-10-20 00:48:282024-10-20 00:48:29

Judging History

你现在查看的是最新测评结果

  • [2024-10-20 00:48:29]
  • 评测
  • 测评结果：WA
  • 用时：3304ms
  • 内存：22544kb
查看
  • [2024-10-20 00:48:28]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
int a[100010];
int n,m;
struct seg{//楼房重建(pushup(log)),解决计算前缀下最小值/最大值位置数量问题
    #define mx(x) tr[x].mx
    #define num(x)  tr[x].num
    #define tag1(x)  tr[x].tag1
    #define tag2(x)  tr[x].tag2
    struct node{
        int mx;int num;//num(x)表示只考虑这一段(l,r)时的答案
        int tag1;int tag2;
    }tr[400010];
    void build(int p,int l,int r,vector<int>& ve){
        mx(p)=num(p)=tag1(p)=tag2(p)=0;
        if(l==r){
            mx(p)=ve[l];num(p)=1;
            return ;
        }
        int mid=(l+r)>>1;
        build(p<<1,l,mid,ve);build(p<<1|1,mid+1,r,ve);
        pushup1(p);
        num(p)=get(p,l,r);
    }
    void pushup1(int p){
        mx(p)=max(mx(p<<1),mx(p<<1|1));
    }
    int pushup2(int p,int l,int r,int len){
        if(l==r)    return mx(p)>=len;
        spread(p,l,r);
        if(mx(p)<len)   return 0;
        int mid=(l+r)>>1;
        if(mx(p<<1|1)>=len)    return num(p)-num(p<<1|1)+pushup2(p<<1|1,mid+1,r,len);
        else return pushup2(p<<1,l,mid,len);
    }
    void spread(int p,int l,int r){
        tag1(p<<1)+=tag1(p),tag1(p<<1|1)+=tag1(p);
        mx(p<<1)+=tag1(p);mx(p<<1|1)+=tag1(p);
        tag1(p)=0;
        if(tag2(p)){
            int mid=(l+r)>>1;
            mx(p<<1)=tag2(p),mx(p<<1|1)=tag2(p);num(p<<1)=mid-l+1,num(p<<1|1)=r-mid;
            tag2(p<<1)=tag2(p),tag2(p<<1|1)=tag2(p);
            tag2(p)=0;
        }
    }
    int get(int p,int l,int r){
        int mid=(l+r)>>1;spread(p,l,r);
        return num(p<<1|1)+((mx(p<<1)<mx(p<<1|1))?0:pushup2(p<<1,l,mid,mx(p<<1|1)));
    }
    void modify(int p,int l,int r,int L,int R,int ad,int t){//0覆盖，1加法
        if(l!=r)    spread(p,l,r);
        if(L<=l&&r<=R){
            if(t==0)    {tag2(p)=ad;mx(p)=ad,num(p)=r-l+1;}
            else {
                tag1(p)+=ad;
                mx(p)+=ad;
            }
            return ;
        }
        int mid=(l+r)>>1;
        if(mid>=L)  modify(p<<1,l,mid,L,R,ad,t);
        if(mid<R)   modify(p<<1|1,mid+1,r,L,R,ad,t);
        pushup1(p);
        num(p)=get(p,l,r);
    }
    void modify(int l,int r,int num,int t){
        modify(1,1,n,l,r,num,t);
    }
    int queryL(int p,int l,int r,int L,int R,int nz){
        if(l==r){
            return mx(p)>nz?l:-1;
        }   
        spread(p,l,r);
        int mid=(l+r)>>1;
        if(mid<R&&mx(p<<1|1)>=nz){
            int t=queryL(p<<1|1,mid+1,r,L,R,nz);
            if(t!=-1)   return t;
        }  
        return queryL(p<<1,l,mid,L,R,nz);
    }
    int queryL(int pz,int num){//pz左边第一个比它大的位置
        if(pz==1)   return -1;
        return queryL(1,1,n,1,pz-1,num);
    }

    int ask(int p,int l,int r,int L,int R){
        if(L<=l&&r<=R)  return mx(p);
        spread(p,l,r);
        int mid=(l+r)>>1;
        if(mid>=L&&mid<R)   return max(ask(p<<1,l,mid,L,R),ask(p<<1|1,mid+1,r,L,R));
        if(mid>=L)  return  ask(p<<1,l,mid,L,R);
        if(mid<R)   return  ask(p<<1|1,mid+1,r,L,R);
        return -1;
    }

    int ask(int l,int r){
        return ask(1,1,n,l,r);
    }

    int query_stack_num(int p,int l,int r,int L,int R,int nz){
        if(L<=l&&r<=R)  {
            return pushup2(p,l,r,nz);
        }
        int mid=(l+r)>>1;
        if(mid>=L&&mid<R)   {
            int nxtl=max(nz,mx(p>>1|1));
            int ans=query_stack_num(p<<1,l,mid,L,R,nxtl)+query_stack_num(p<<1|1,mid+1,r,L,R,nz);
            return ans;
            // return query_stack_num(p<<1,l,mid,L,R,nxtl)+query_stack_num(p<<1|1,mid+1,r,L,R,nz);
        }
        if(mid>=L)  return  query_stack_num(p<<1,l,mid,L,R,nz);
        if(mid<R)   return  query_stack_num(p<<1|1,mid+1,r,L,R,nz);
        return -1;
    }

    int query_stack_num(int l,int r,int nz){
        return query_stack_num(1,1,n,l,r,nz);
    }
};
seg sg;
void solve(){
    cin>>n>>m;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    struct node{
        int op,l,r,x;
    };
    vector<node> ak(m+1);
    vector<int> ans(m+1,0);
    for(int i=1;i<=m;i++){
        cin>>ak[i].op>>ak[i].l>>ak[i].r>>ak[i].x;
        if(n==321)  cerr<<ak[i].op<<' '<<ak[i].l<<' '<<ak[i].r<<' '<<ak[i].x<<'\n';
    }
    auto ope=[&](vector<int>& ve,vector<node>& qry)->void {
        sg.build(1,1,n,ve);
        // cerr<<'\n';
        for(int i=1;i<=m;i++){
            auto [op,l,r,x]=qry[i];
            if(op==1){
                sg.modify(l,r,x,1);
            }
            else if(op==2){
                sg.modify(l,r,x,0);
            }
            else if(l!=-1&&l<=r){
                int w=sg.ask(x,x);
                int pz=sg.queryL(x,w);
                ans[i]+=max(r-max(l,pz)+1,0ll);
                if(pz>l) ans[i]+=sg.query_stack_num(l,min(r,pz-1),sg.ask(pz,pz));
            }
        }
    };
    vector<node> qry1(m+1),qry2(m+1);
    for(int i=1;i<=m;i++){
        if(ak[i].op!=3) qry1[i]=qry2[i]=ak[i];
        else{
            auto [op,l,r,x]=ak[i];
            if(x<=r&&x>=l)  {
                ans[i]++;
                qry1[i]={3,l,x-1,x};
                qry2[i]={3,x+1,r,x};
            }
            else if(x<l){
                qry1[i]={3,-1,-1,x};
                qry2[i]={3,l,r,x};
            }
            else{
                qry1[i]={3,l,r,x};
                qry2[i]={3,n+2,n+2,x};
            }
        }
    }
    for(auto& [op,l,r,x]:qry2){
        l=n-l+1,r=n-r+1;swap(l,r);
        if(op==3)   x=n-x+1;
    }

    ope(a,qry1);
    reverse(a.begin()+1,a.end());
    ope(a,qry2);
    for(int i=1;i<=m;i++){
        if(ak[i].op==3) cout<<ans[i]<<'\n';
    }   
}
signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);

    int _ = 1;
    cin >> _;
    while (_--) solve();

    return 0;
}
/*
1
10 5
1 2 1 2 1 1 1 1 1 1
2 1 3 1
2 2 5 2
2 6 6 3
1 9 9 1
3 2 10 10
*/
/*
1 2 2 2 2 3 1 1 1 1
*/
源文件, 语言: C++23

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3824kb

input:

1
10 10
1 3 2 5 2 3 1 6 4 5
3 5 7 8
3 5 7 4
1 1 5 2
3 1 10 4
3 1 10 8
2 8 8 8
3 1 10 8
3 1 10 4
2 4 8 1
3 1 2 10

output:

3
3
10
7
10
8
2

result:

ok 7 lines

Test #2:

score: -100
Wrong Answer
time: 3304ms
memory: 22544kb

input:

200
321 43
168330405 102091681 86278243 227886812 609333939 211045240 332465535 212315420 510322126 700237719 102348318 320419595 409640374 582249257 245617532 643949598 748863235 405762764 358055464 585833725 429993246 60296212 632603910 229141445 696836739 297883078 545245133 44079558 92873286 347...

output:

0
58
70
2
2
0
50
5
9
87
58
58
97
247
106
92
43
335
18
32
0
3
48
0
18
5
0
3
5
72
59
0
7
64
128
58
15
0
61
28
3
42
0
1
0
137
10
19
12
27
123
35
168
184
110
118
115
0
0
189
7
104
41
8
104
75
2
99
130
13
105
185
0
0
41
0
0
29
0
7
0
79
16
73
28
22
3
9
8
0
11
74
0
49
0
46
50
0
144
5
60
68
32
0
75
7
0
227
...

result:

wrong answer 1st lines differ - expected: '1', found: '0'
English 繁體中文 简体中文

伺服器時間: 2024-12-04 23:11:22 | 開源專案