QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#662244#7007. Rikka with Data Structurespengpeng_fudanAC ✓2293ms23844kbC++236.2kb2024-10-20 22:13:152024-10-20 22:13:16

Judging History

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

  • [2024-10-20 22:13:16]
  • 评测
  • 测评结果：AC
  • 用时：2293ms
  • 内存：23844kb
查看
  • [2024-10-20 22:13:15]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
struct seg{
    #define mx(x)    tr[x].mx
    #define num(x)   tr[x].num
    #define tag1(x)  tr[x].tag1
    #define tag2(x)  tr[x].tag2
    int n;
    struct node{
        int mx,num,tag1,tag2;
    }tr[400010];
    void pushup1(int p,int l,int r){
        mx(p)=max(mx(p<<1),mx(p<<1|1));
        num(p)=get(p,l,r);
    }
    int pushup2(int p,int l,int r,int nz){
        if(l==r)    return mx(p)>=nz;
        spread(p,l,r);
        int mid=(l+r)>>1;
        if(mx(p<<1|1)>=nz)  return num(p)-num(p<<1|1)+pushup2(p<<1|1,mid+1,r,nz);
        else return pushup2(p<<1,l,mid,nz);
    }
    int get(int p,int l,int r){
        int mid=(l+r)>>1;
        return num(p<<1|1)+(mx(p<<1|1)>mx(p<<1)?0:pushup2(p<<1,l,mid,mx(p<<1|1)));
    }
    void intt(int sz,vector<int>& ve){
        n=sz;
        build(1,1,n,ve);
    }
    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,l,r);
        // cerr<<l<<' '<<r<<' '<<mx(p)<<' '<<num(p)<<'\n';
    }
    void spread(int p,int l,int r){
        if(tag2(p)){
            mx(p<<1)=mx(p<<1|1)=tag2(p);
            int mid=(l+r)>>1;
            num(p<<1)=mid-l+1,num(p<<1|1)=r-mid;
            tag1(p<<1)=tag1(p<<1|1)=0;tag2(p<<1)=tag2(p<<1|1)=tag2(p);
            tag2(p)=0;
        }
        if(tag1(p)){
            mx(p<<1)+=tag1(p);mx(p<<1|1)+=tag1(p);
            tag1(p<<1)+=tag1(p);tag1(p<<1|1)+=tag1(p);
            tag1(p)=0;
        } 
    }
    void modify(int p,int l,int r,int L,int R,int nz,int t){
        if(L<=l&&r<=R){
            if(t==1)    {mx(p)+=nz;tag1(p)+=nz;}
            else {mx(p)=nz,tag1(p)=0;tag2(p)=nz;num(p)=r-l+1;}
            return ;
        }
        spread(p,l,r);
        int mid=(l+r)>>1;
        if(mid>=L)  modify(p<<1,l,mid,L,R,nz,t);
        if(mid<R)   modify(p<<1|1,mid+1,r,L,R,nz,t);
        pushup1(p,l,r);
    }
    void modify(int l,int r,int nz,int t){
        modify(1,1,n,l,r,nz,t);
    }
    pair<int,int> queryL(int p,int l,int r,int L,int R,int nz){
        if(l==r){
            if(mx(p)>nz)    return {l,mx(p)};
            else return {-1,-1};
        }
        spread(p,l,r);
        int mid=(l+r)>>1;
        if(mid<R&&mx(p<<1|1)>nz){
            pair<int,int> t=queryL(p<<1|1,mid+1,r,L,R,nz);
            if(t.first!=-1)   return t;
        }
        return queryL(p<<1,l,mid,L,R,nz);
    }
    pair<int,int> queryL(int l,int nz){
        return queryL(1,1,n,1,l,nz);
    }
    pair<int,int> query_stack_num(int p,int l,int r,int L,int R,int nz){
        if(L<=l&&r<=R)  return {mx(p),pushup2(p,l,r,nz)};
        int mid=(l+r)>>1;
        spread(p,l,r);
        if(mid>=L&&mid<R)   {
            pair<int,int> nxtr=query_stack_num(p<<1|1,mid+1,r,L,R,nz);
            pair<int,int> nxtl=query_stack_num(p<<1,l,mid,L,R,max(nxtr.first,nz));
            return {max(nxtr.first,nxtl.first),nxtr.second+nxtl.second};
        }
        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,-1};
    }
    int query_stack_num(int l,int r,int nz){
        return query_stack_num(1,1,n,l,r,nz).second;
    }
    int get_num(int p,int l,int r,int pz){
        if(l==r)    return mx(p);
        spread(p,l,r);
        int mid=(l+r)>>1;
        if(mid>=pz) return get_num(p<<1,l,mid,pz);
        else return get_num(p<<1|1,mid+1,r,pz);
    }
    int get_num(int pz){
        return get_num(1,1,n,pz);
    }
    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);
    }
}sg1,sg2;
void solve(){
    int n,q;
    cin>>n>>q;
    vector<int> a1(n+1),a2(n+1);
    for(int i=1;i<=n;i++)   {cin>>a1[i];a2[n-i+1]=a1[i];}
    sg1.intt(n,a1);sg2.intt(n,a2);
    for(int i=1;i<=q;i++){
        int op,l,r,x;
        cin>>op>>l>>r>>x;
        if(op==1||op==2)    sg1.modify(l,r,x,op),sg2.modify(n-r+1,n-l+1,x,op);
        else{
            int ans=(l<=x&&x<=r);
            auto get1=[&](int lo,int ro,int x)->int {
                int res=0;
                auto [pz,nz]=sg1.queryL(x-1,sg1.get_num(x));
                if(pz<=ro)   {
                    res+=max(0ll,ro-max(lo,pz)+1);
                    if(pz>lo)    res+=sg1.query_stack_num(lo,pz-1,nz);
                }
                else res+=sg1.query_stack_num(lo,ro,sg1.ask(ro+1,x)); 
                return res;
            };
            auto get2=[&](int lo,int ro,int x)->int {
                int res=0;
                auto [pz,nz]=sg2.queryL(x-1,sg2.get_num(x));
                if(pz<=ro)   {
                    res+=max(0ll,ro-max(lo,pz)+1);
                    if(pz>lo)    res+=sg2.query_stack_num(lo,pz-1,nz);
                }
                else res+=sg2.query_stack_num(lo,ro,sg2.ask(ro+1,x));
                // cerr<<lo<<' '<<ro<<' '<<sg2.ask(ro+1,x)<<' '<<sg2.query_stack_num(lo,ro,sg2.ask(ro+1,x))<<'\n'
                return res;
            };
            int lo=l,ro=min(r,x-1);
            if(lo<=ro)  ans+=get1(lo,ro,x);
            lo=max(x+1,lo),ro=r;
            if(lo<=ro)  ans+=get2(n-ro+1,n-lo+1,n-x+1);
            cout<<ans<<'\n';
        }
    }
}
signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int _ = 1;
    cin >> _;
    while (_--) solve();

    return 0;
}
/*
1
100 1
2 8 5 1 10 5 9 9 3 5 6 6 2 8 2 2 6 3 8 7 2 5 3 4 3 3 2 7 9 6 8 7 2 9 10 3 8 10 6 5 4 2 3 4 4 5 2 2 4 9 8 5 3 8 8 10 4 2 10 9 7 6 1 3 9 7 1 3 5 9 7 6 1 10 1 1 7 2 4 9 10 4 5 5 7 1 7 7 2 9 5 10 7 4 8 9 9 3 10 2
3 71 73 30

*/
/*
1
10 3
1 1 2 3 1 2 3 1 1 2 
2 3 5 3
1 1 2 1
3 1 5 10


*/

/*
1
10 2
1 2 1 4 3 2 4 5 6 3
2 1 9 1
3 1 9 10

*/
/*
1 1 10 100000
2 3 4 532423
3 5 7 1
2 1 2 213123
1 4 6 21331
3 1 5 2
3 3 4 5
*/
源文件, 语言: C++23

这程序好像有点Bug，我给组数据试试？

詳細信息

Test #1:

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

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: 0
Accepted
time: 2146ms
memory: 23844kb

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:

1
59
70
2
2
1
50
5
9
149
58
189
97
247
106
103
43
335
18
87
165
13
68
0
101
5
0
0
5
148
60
0
62
85
171
64
60
0
121
56
0
42
0
167
15
142
15
152
114
28
123
35
219
235
110
120
117
0
0
239
7
104
41
19
104
75
2
114
240
6
143
196
15
0
70
42
93
87
212
4
0
119
103
86
85
52
5
26
41
0
11
74
0
128
20
128
108
0...

result:

ok 537510 lines

Test #3:

score: 0
Accepted
time: 2293ms
memory: 23348kb

input:

200
1000 1000
713461821 335659317 728622735 565055025 676189278 198078223 558499753 212651574 230931147 569362123 355576596 640258410 277799062 534119954 47415612 181943136 899691295 288861951 414045724 980772190 88609953 779771556 963245511 3359968 448040102 686663557 390217443 748126228 121334413 ...

output:

4
125
0
0
0
239
280
135
103
108
484
5
687
141
342
730
280
399
215
781
325
109
139
4
134
705
430
0
0
440
528
43
369
28
0
457
5
23
884
559
65
279
378
152
0
0
112
173
573
0
0
63
913
736
777
31
723
290
167
711
309
7
344
290
59
127
553
0
138
452
367
237
586
252
147
430
0
26
113
0
791
22
0
574
87
401
16
2...

result:

ok 593920 lines
English 繁體中文 简体中文

伺服器時間: 2024-12-02 21:45:44 | 開源專案