QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#249677 | #6533. Traveling in Cells | dd | TL | 1826ms | 59216kb | C++20 | 4.7kb | 2023-11-12 14:00:00 | 2023-11-12 14:00:01 |
Judging History
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...