QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#249677#6533. Traveling in CellsddTL 1826ms59216kbC++204.7kb2023-11-12 14:00:002023-11-12 14:00:01

Judging History

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

  • [2023-11-12 14:00:01]
  • 评测
  • 测评结果:TL
  • 用时:1826ms
  • 内存:59216kb
  • [2023-11-12 14:00:00]
  • 提交

answer

//#pragma GCC optimize ("Ofast,unroll-loops")
//#pragma GCC target ("avx2")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define notall(x) x.begin()+1,x.end()
#define all(x) x.begin(),x.end()
#define mul_t int _t;cin>>_t;while(_t--)
const int int_inf = 1000000100;
const ll ll_inf = 1000000000000000100;
//writers
template<class T>
void writeln(const T &t) {
    cout << t << '\n';
}
template<class T, class...args>
void writeln(const T &t, const args &...rest) {
    cout << t << ' ';
    writeln(rest...);
}
template<class T1>
void writeln(const vector<T1> &v) {
    for (auto c : v)
        cout << c << ' ';
    cout << ' ' << '\n';
}
template<class T1, class T2>
void writeln(const vector<T1> &v, T2 n) {
    for (T2 i = 1; i <= n; i++)
        cout << v[i] << ' ';
    cout << ' ' << '\n';
}
template<class T1, class T2>
void writeln(const pair<T1, T2> p) {
    cout << p.first << ' ' << p.second << ' ' << '\n';
}

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
struct chash {
    int operator()(int x) const { return x ^ RANDOM; }
};
typedef gp_hash_table<int, int,chash> hash_t;

const int maxn=1e5+5;
int n,q,p,x,op;
ll bitsum[maxn];
hash_t col[maxn];
int c[maxn];
ll a[maxn];
void addsum(int pos,ll num)
{
    while(pos<=n)bitsum[pos]+=num,pos+=(pos&-pos);
}

ll querysum(int l,int r)
{
    ll ans=0;
    while(r)
    {
        ans+=bitsum[r],r-=(r&-r);
    }
    --l;
    while(l)
    {
        ans-=bitsum[l],l-=(l&-l);
    }
    return ans;
}

int querycol(int l,int r,vector<int>&cc)
{
    int ans=0;
    while(r)
    {
        for(auto&c:cc)
        {
            ans+=col[r][c];
        }
        r-=(r&-r);
    }
    --l;
    while(l)
    {
        for(auto&c:cc)
        {
            ans-=col[l][c];
        }
        l-=(l&-l);
    }
    return ans;
}

void addcol(int pos,int c,int flag)
{
    while(pos<=n)
    {
        col[pos][c]+=flag;
        if(col[pos][c]==0)col[pos].erase(c);
        pos+=(pos&-pos);
    }
}

void solve(){
    cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
        cin>>c[i];
        addcol(i,c[i],1);
    }
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        addsum(i,a[i]);
    }
    for(int i=1;i<=q;i++)
    {
        cin>>op>>p>>x;
        if(op==1)
        {
            int lst=c[p];
            addcol(p,lst,-1);
            c[p]=x;
            addcol(p,x,1);
        }
        else if(op==2)
        {
            ll lst=a[p];
            addsum(p,-lst);
            a[p]=x;
            addsum(p,x);
        }
        else
        {
            vector<int>nowcol(x);
            for(auto&c:nowcol)cin>>c;
            int l=1,r=p-1,ans=p,ans2=p;
            while(l<=r)
            {
                int mid=(l+r)>>1;
                if(querycol(mid,p,nowcol)==p-mid+1)r=mid-1,ans=mid;
                else l=mid+1;
            }
            l=p+1,r=n;
            while(l<=r)
            {
                int mid=(l+r)>>1;
                if(querycol(p,mid,nowcol)==mid-p+1)l=mid+1,ans2=mid;
                else r=mid-1;
            }
            //writeln(ans,ans2);
            writeln(querysum(ans,ans2));
        }
    }
    fill(bitsum+1,bitsum+n+1,0);
    for(int i=1;i<=n;i++)col[i].clear();
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout << fixed << setprecision(15);
    mul_t
    solve();
}
/*
1.深呼吸,不要紧张,慢慢读题,读明白题,题目往往比你想的简单。
2.暴力枚举:枚举什么,是否可以使用一些技巧加快枚举速度(预处理、前缀和、数据结构、数论分块)。
3.贪心:需要排序或使用数据结构(pq)吗,这么贪心一定最优吗。
4.二分:满足单调性吗,怎么二分,如何确定二分函数返回值是什么。
5.位运算:按位贪心,还是与位运算本身的性质有关。
6.数学题:和最大公因数、质因子、取模是否有关。
7.dp:怎么设计状态,状态转移方程是什么,初态是什么,使用循环还是记搜转移。
8.搜索:dfs 还是 bfs ,搜索的时候状态是什么,需要记忆化吗。
9.树上问题:是树形dp、树上贪心、或者是在树上搜索。
10.图论:依靠什么样的关系建图,是求环统计结果还是最短路。
11.组合数学:有几种值,每种值如何被组成,容斥关系是什么。
12.交互题:log(n)次如何二分,2*n 次如何通过 n 次求出一些值,再根据剩余次数求答案。
13.如果以上几种都不是,多半是有一个 point 你没有注意到,记住正难则反。
*/

詳細信息

Test #1:

score: 100
Accepted
time: 5ms
memory: 25200kb

input:

2
5 10
1 2 3 1 2
1 10 100 1000 10000
3 3 1 3
3 3 2 2 3
2 5 20000
2 3 200
3 3 2 1 3
3 3 3 1 2 3
1 3 4
2 1 100000
1 2 2
3 1 2 1 2
4 1
1 2 3 4
1000000 1000000 1000000 1000000
3 4 4 1 2 3 4

output:

100
110
1200
21211
100010
4000000

result:

ok 6 numbers

Test #2:

score: 0
Accepted
time: 326ms
memory: 25540kb

input:

20000
15 15
1 1 3 3 2 3 3 3 3 3 2 3 2 3 3
634593973 158136379 707704004 998369647 831633445 263092797 937841412 451774682 552617416 483763379 50360475 794662797 74247465 537217773 901809831
3 6 4 1 3 5 10
3 5 7 1 2 3 4 5 9 10
3 4 3 3 8 9
2 13 608033129
3 15 2 3 5
1 9 3
3 8 4 1 3 7 10
2 6 727472865
3...

output:

2689089686
8377825475
1706073651
1439027604
2689089686
792730352
8904867081
8904867081
8270273108
831633445
692051585
2782432626
697783016
883944422
184057757
287523250
184057757
696388752
184057757
1675459344
2667693025
2614711258
4006992373
1767091974
5348541057
5348541057
390631780
2290216252
942...

result:

ok 200062 numbers

Test #3:

score: 0
Accepted
time: 465ms
memory: 24880kb

input:

2000
150 150
8 3 8 8 8 6 8 4 2 7 6 8 8 5 8 7 7 8 5 6 8 8 6 8 8 8 8 7 8 6 6 8 8 8 6 2 3 4 8 8 7 8 5 8 2 6 8 7 8 8 6 8 6 8 3 8 8 8 8 4 7 8 7 3 7 6 7 5 5 8 6 8 8 6 3 8 6 7 6 8 8 7 4 8 6 7 8 7 7 7 7 8 8 8 8 2 5 2 8 8 6 7 6 3 8 8 7 8 8 8 6 6 8 6 6 7 5 8 8 8 7 8 7 7 6 8 8 8 8 8 8 6 5 7 5 5 8 7 8 7 7 7 6 5...

output:

4449391171
3290849667
852793841
5178673994
995994209
11431868919
4327723427
5071541023
3032743466
962345334
2997656427
4534278452
3851900075
3611231417
5071541023
1477584218
1299005818
1299005818
2145605244
854143763
886347565
2081234124
2333808475
2455955801
4179722063
2328504333
1473735464
4107685...

result:

ok 199987 numbers

Test #4:

score: 0
Accepted
time: 1333ms
memory: 35396kb

input:

10
30000 30000
3 4 2 4 4 4 4 3 4 3 4 3 4 3 4 4 2 4 4 4 4 4 3 3 3 4 3 4 3 4 3 3 4 2 4 3 3 3 3 4 3 4 4 4 4 2 3 3 4 2 3 4 4 4 4 1 4 4 4 4 4 4 4 4 3 3 3 4 4 4 4 4 2 3 4 4 4 4 3 4 4 3 3 3 4 4 3 4 4 2 3 4 4 4 4 3 2 4 3 4 3 2 4 4 3 4 2 2 4 4 4 4 2 4 3 2 4 4 3 4 4 4 2 4 4 3 2 3 2 3 3 3 4 2 4 3 4 1 4 3 4 4 4...

output:

6959437173
934970676
72461245502
8365928740
8384151048
984567228
12482909122
1904927816
15134139942
3759040688
92670874909
332468911
5936663371
3562978848
1300592004
10314009201
5581540905
131246926443
15087184135864
4077066271
1124704817
1520626740
4388174158
744377942
2770411457
6231852240
1508724...

result:

ok 200135 numbers

Test #5:

score: 0
Accepted
time: 1826ms
memory: 59216kb

input:

3
100000 100000
6 6 2 6 5 3 6 5 4 6 4 6 6 6 6 5 2 5 2 6 6 6 1 6 5 6 4 5 6 6 5 4 5 4 3 4 5 5 6 6 5 6 6 5 2 5 6 5 4 2 5 6 6 6 5 2 5 6 6 4 5 6 3 3 6 5 6 5 5 5 5 4 4 4 4 3 6 5 4 5 6 5 6 6 6 6 3 6 5 6 5 4 3 5 6 4 5 3 6 5 3 5 6 4 6 5 4 5 5 5 2 5 4 6 6 3 5 5 5 5 5 4 5 5 6 5 5 6 6 6 5 5 4 6 5 4 4 2 6 6 6 5 ...

output:

753014823
938372065
5655899645
168297301
14372254310
1066586326
3520855082
2591792266
2321844837
64378192092
250581310
1845085639
1402247975
198007248
2157074263
2743531397
3433471688
10332600792
1085086491
4845484125
50019185900042
4036199358
154762798
50019185900042
1221387905
11240790307
10537215...

result:

ok 199749 numbers

Test #6:

score: -100
Time Limit Exceeded

input:

3
100000 100000
173 276 418 362 183 321 401 316 193 426 212 126 206 409 382 443 405 412 259 233 356 355 340 41 354 447 421 464 436 436 329 239 427 415 452 424 174 294 220 413 293 456 140 304 438 462 418 345 160 296 443 234 455 452 396 347 438 413 235 416 363 186 340 285 340 457 392 359 451 310 431 1...

output:

832547880
1825993219
676042867
310750190
650714631
657481975
1279322
838513014
453432678
940357183
846050641
631145680
278723792
689448062
154699248
45678908
56518237
839298643
611124630
499104412
324172054
742064269
626600147
728123335
602272914
45485542
868574266
876207167
342300121
917221167
7055...

result: