QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#746053 | #2917. Even Substrings | zeyu | AC ✓ | 6482ms | 137780kb | C++23 | 4.1kb | 2024-11-14 13:09:58 | 2024-11-14 13:10:04 |
Judging History
answer
#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define pl pair<ll, ll>
#define pi pair<int, int>
#define minpq priority_queue<ll, vector<ll>, greater<ll>>
using namespace std;
#if 1
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '['; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "]";}
void _print() {cerr << endl << flush;}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#define debug(x...) cerr << "*["<<__LINE__<<"]\t"<< #x << " = "; _print(x)
#endif
const ll mod = 1e9 + 7;
template<typename T> bool chkmin(T &a, T b){return (b < a) ? a = b, 1 : 0;}
template<typename T> bool chkmax(T &a, T b){return (b > a) ? a = b, 1 : 0;}
ll gcd(ll a, ll b) {if(b == 0){return a;} return gcd(b, a % b);}
struct segtree{
vector<int> cnt[64];
vector<int> lazy;
int sz;
void init(int n){
sz = 1;
while(sz < n) sz <<= 1;
for (int i = 0; i < 64; i ++){
cnt[i].assign(2 * sz, 0);
}
lazy.assign(2 * sz, 0);
}
void push(int x, int lx, int rx){
for (int i = 0; i < 64; i ++){
if ((i ^ lazy[x]) > i) swap(cnt[i][x], cnt[i ^ lazy[x]][x]);
}
if (rx - lx != 1){
lazy[2 * x + 1] ^= lazy[x];
lazy[2 * x + 2] ^= lazy[x];
}
lazy[x] = 0;
}
void build(vector<int>& a, int x, int lx, int rx){
if (rx - lx == 1){
if (lx < a.size()) cnt[a[lx]][x] = 1;
return;
}
int mid = (lx + rx) >> 1;
build(a, 2 * x + 1, lx, mid);
build(a, 2 * x + 2, mid, rx);
for (int i = 0; i < 64; i ++){
cnt[i][x] = cnt[i][2 * x + 1] + cnt[i][2 * x + 2];
}
}
void build(vector<int>& a){
build(a, 0, 0, sz);
}
void upd(int l, int r, int v, int x, int lx, int rx){
push(x, lx, rx);
if (lx >= r || rx <= l) return;
if (lx >= l && rx <= r){
lazy[x] ^= v;
//we have to push here! since we need to compute sum when we go up
push(x, lx, rx);
return;
}
int mid = (lx + rx) >> 1;
upd(l, r, v, 2 * x + 1, lx, mid);
upd(l, r, v, 2 * x + 2, mid, rx);
for (int i = 0; i < 64; i ++){
cnt[i][x] = cnt[i][2 * x + 1] + cnt[i][2 * x + 2];
}
}
void upd(int l, int r, int v){
upd(l, r, v, 0, 0, sz);
}
vector<int> calc(int l, int r, int x, int lx, int rx){
push(x, lx, rx);
vector<int> ans(64, 0);
if (lx >= r || rx <= l) return ans;
if (lx >= l && rx <= r){
for (int i = 0; i < 64; i ++) ans[i] = cnt[i][x];
return ans;
}
int mid = (lx + rx) >> 1;
vector<int> ans1 = calc(l, r, 2 * x + 1, lx, mid), ans2 = calc(l, r, 2 * x + 2, mid, rx);
for (int i = 0; i < 64; i ++) ans[i] = ans1[i] + ans2[i];
return ans;
}
vector<int> calc(int l, int r){
return calc(l, r, 0, 0, sz);
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
string s; cin >> s;
int q; cin >> q;
int n = s.size(), val = 0;
segtree seg;
seg.init(n + 1);
vector<int> a(n + 1);
for (int i = 0; i < n; i ++){
val ^= 1 << (s[i] - 'a');
a[i + 1] = val;
}
seg.build(a);
while(q --){
int op; cin >> op;
if (op == 1){
int l, r; cin >> l >> r; l --;
ll ans = 0;
vector<int> cur = seg.calc(l, r + 1);
for (int i = 0; i < 64; i ++){
ans += (ll)cur[i] * (ll)(cur[i] - 1) / 2;
}
cout << ans << '\n';
} else{
int i; char x; cin >> i >> x;
seg.upd(i, n + 1, (1 << (x - 'a')) ^ (1 << (s[i - 1] - 'a')));
s[i - 1] = x;
}
}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3656kb
input:
a 7 1 1 1 2 1 b 1 1 1 2 1 c 1 1 1 2 1 a 1 1 1
output:
0 0 0 0
result:
ok 4 lines
Test #2:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
cc 13 1 1 2 2 1 b 1 1 2 2 2 b 1 1 2 2 2 f 1 1 2 2 1 f 1 1 2 2 1 c 1 1 2 2 2 c 1 1 2
output:
1 0 1 0 1 0 1
result:
ok 7 lines
Test #3:
score: 0
Accepted
time: 204ms
memory: 4140kb
input:
dbccccdfdbfccbfedbfbcbfffaeeaafcbfdebaeaaffcacddeaefaaeecabebfbbcbffadadeefbaffabdfecffbaaeafcfffdeadcccfafbbaedfdfdccdccafeabcbbbfbbfdcaceafccbcdddacbabbabaeeacaefeecffcffdfabddbdbcadeefcdbcaaefdbabededcdfbdcdcfcedafacdaedeccbaddeabbbffdeadcbcdeadbacfddbabcfcabeedcbabecadcfbfedecfebbfcfdcffdfffabde...
output:
4442 411 196 61 223 677 1473 177 2 1721 1146 24 1444 362 950 206 90 2210 108 248 2 1912 887 1949 216 41 1509 82 292 2021 79 3063 1334 1215 4254 294 2 517 48 44 454 21 209 966 241 35 110 5790 3698 2240 2249 899 0 952 3645 1378 2441 3060 838 5097 371 5671 231 459 6558 605 369 51 2232 1054 2801 1586 26...
result:
ok 25157 lines
Test #4:
score: 0
Accepted
time: 190ms
memory: 4420kb
input:
ababbabababbabababbabababbabababbabababbabababbabababbabababbabababbabababbabababbabababbabababbabababbabababbabababbabababbabababbabababbabababbabababbabababbabababbabababbabababbabababbabababbabababbabababbabababbabababbabababbabababbabababbabababbabababbabababbabababbabababbabababbabababbabababba...
output:
94 0 41 14232 4570 3782 24677 16481 19841 112119 2416 2346 61300 5673 16842 33154 400 100 5217 853 194 63142 100640 778 1170 13124 11738 31756 2927 4985 15232 33943 21400 23060 2632 19712 36601 761 6445 15146 60554 15 4140 196 14974 3348 684 9634 13 6869 11654 71554 96962 467 802 781 433 79390 422 8...
result:
ok 24897 lines
Test #5:
score: 0
Accepted
time: 6482ms
memory: 137604kb
input:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
467074062 275012472 719948856 836402005 2973578059 25923372 1092382441 87928186 343819507 36562992 153758109 312878201 959083370 268842966 388135674 267016211 17471821 18636489 445740295 447512184 170031806 574467571 545727719 174830757 141942228 580871873 724813275 190760037 9957588 449412008 51877...
result:
ok 99998 lines
Test #6:
score: 0
Accepted
time: 4677ms
memory: 137640kb
input:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
198007368 1580976882 356798016 379900356 1548743368 2593317 737604882 131652676 866126650 3829737309 203867836 207709082 506003763 1816284154 1957822198 3095675668 1431846377 2912142 123187801 66674810 421163345 70517181 25954173 273224370 2214438682 676647396 3861767845 388214299 801251344 89507269...
result:
ok 99781 lines
Test #7:
score: 0
Accepted
time: 6363ms
memory: 137688kb
input:
abcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdef...
output:
556930 84983592 650052459 196544989 627344650 38999700 93192827 602813289 63430261 111659262 358680 397752984 214693980 288726075 8233965 6747960 318026761 648090803 50957118 214573565 135121389 2975808 486860533 194000884 350345343 1983175 487734582 23538982 504106355 36944571 58856848 481305116 29...
result:
ok 180039 lines
Test #8:
score: 0
Accepted
time: 6444ms
memory: 137472kb
input:
abcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdef...
output:
250551126 136908820 736099884 11630160 705076960 92408741 41464588 56571450 150482032 26462579 1534455 266165252 161680310 24336919 60737609 875978 53793927 150190726 61960561 25732493 10268986 43220891 263702474 302220 130242653 755440 120417954 139438839 64297462 168254620 1434960 55166736 1127069...
result:
ok 100305 lines
Test #9:
score: 0
Accepted
time: 4518ms
memory: 137704kb
input:
babbaaaaabaabbbbabbbaaabbbbabababaabababbbbbbbbbaaaaaabbbabbbbaaabaabaabbabaabaaababbbbaaaabbaababbaaaabbaabaaababbabbaaabbabbabaabbbabaaaaaabbbaaabbbbbbabababbbabbabbbabaaabbabbababaaababaabaaabbbaabababbaaaaaaabaabbaabbabbaaaaaababbbbbaababaabababbbbabbbabbbbaababbabbababaabaaabababbbbabababaaaaaa...
output:
583821040 624742996 2863745945 1514907 183585996 1158386457 19158222 25045784 4182314 242394303 2788601821 2660258200 1955480452 2199645 499392202 82774422 12542304 3480187529 9240172 2297754765 1155047444 1731576025 264665488 139589587 149403967 143964258 963249026 538313985 274811502 166925453 156...
result:
ok 99693 lines
Test #10:
score: 0
Accepted
time: 5403ms
memory: 137668kb
input:
abbccccbbcaccbbccaccccaccacccaaabbaccbbacbcabcbbacabcccbbbcbbacbabbbababbbbbbcacbcccaacccccccbaabccaaaacbcabaaabcbbabcbacaaabcbbccbacabbbabcccacbacccbaabcbbacbacbbabbacbbbcccbcaacbbaacbabbbbbbcabacbabaccbbabccbccabcabbaabaacabaccaabcaaacabbabcbbabcccaccbacaaabbcbaaaaccbaccacaacabbcbcaaabacbabaabcbbb...
output:
48875308 1230243385 5851216 110873772 843191359 2076296798 310948468 1106151191 301384639 264640010 367736641 772588 200873 1177458926 16772676 251034801 844768102 29183618 1080262773 10873421 26850594 1276147 64528463 523351400 3031439 832744180 742522731 67979405 27825898 802720402 189070599 80830...
result:
ok 99844 lines
Test #11:
score: 0
Accepted
time: 6405ms
memory: 137780kb
input:
ffeebceaecdcfeceadeddfebfcbbbfceacddccefacdebcbcbadabebfccaadcedceadafbbdbfacebebbbdabaffaabcbfeacdfcfffbdeddeefdafaedeccecbccecbaeebfedfbacaeddbbaafcefaefcadafccfbfdecadbccdcccecffbefcebcfbccacfcfcfeefdbfecceefbcdbaceeacdeeecdddeaddebfbceaaeaafdefecaacefedcbeffaffadacccecdcdcbaaddaddafbabcdaadbdbfe...
output:
21174434 44213599 1179766 3635894 50987552 54312832 99167497 14825776 5285364 115796134 30703695 142134967 200466754 267159064 646056 3067770 114467383 283400669 16658231 177633 1057966 1536493 238895182 38385762 648306 37039995 7064846 116856510 11222350 16040287 21291125 3082430 63111022 12680970 ...
result:
ok 99701 lines
Test #12:
score: 0
Accepted
time: 3418ms
memory: 137508kb
input:
abababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababab...
output:
1250000000 1250000000 1250000000 1250000002 1250000000 1250000000 1250000002 1250000002 1250000000 1250000000 1250000002 1250000002 1250000000 1250000000 1250000002 1250000002 1250000002 1250000004 1250000002 1250000000 1250000002 1250000000 1250000000 1250000000 1250000006 1250000012 1250000000 125...
result:
ok 99767 lines
Test #13:
score: 0
Accepted
time: 4580ms
memory: 137668kb
input:
abcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdef...
output:
416633334 416633334 416633334 416633334 212067198 199933370 199929129 199924888 199920647 162502885 162500373 162497553 162497554 162492400 126638308 150569933 150568624 134068956 110864019 110410809 110410810 110410811 110410814 108939140 108939969 121307975 121307204 121305809 130160354 130159600 ...
result:
ok 99781 lines
Test #14:
score: 0
Accepted
time: 5502ms
memory: 137644kb
input:
fdeabebecaedfbfbccbaccceeadebffadcfbbcaecafeeadcdcaaaeebffbffdbeefaccaedaebbdbfdccaaffdaedabefcfeafcbacedfcfdfebbfdbebfbcddbebcbdacbbefaccbbaefbbcafadbcbbbacafbefaeadbbfcebaafcaaebaaeeccedebdddccfdfdcfaebaeeeaeccfceaacabeeaadaeccdfdbacdffcafcadedfeeebbcdffbbfccdcececbecfbffabebbaeafffeabedffdacddfcc...
output:
78137986 78124985 78124976 78124998 78124972 78124897 78149433 78146182 78154072 78149052 78149215 78144534 78138479 78158506 78131893 78127599 78115729 78114614 78130440 78159165 78171269 78116182 78116266 78126455 78112508 78112016 78111396 78129723 78129819 78153948 78154006 78160279 78160445 781...
result:
ok 40380 lines
Test #15:
score: 0
Accepted
time: 4531ms
memory: 137780kb
input:
acdffdcbdddfcadcdbfbebeecbaabbecddaddbaedcffeacfbececbddfeaeeacdbdcfbdaceffeecabcacdddfebcbabcbdbdceabbefbdcedecacadfcaafcedafccdfbbdbecdecdcfeaedfcdfcacbbfcdbbcaabfcfabafacdcbdddecdeffcceeefadaefedeafeeabfdcfbbebddfdeedaeebdebddddbffffeafafbbcdadaddedfdbcbcbfdfdedbfafddfbcbfbdbaceadecabfafcbbdadfbd...
output:
78123460 78123417 78123413 78123393 78143725 78143775 78143716 78143610 78143661 78143617 78143608 78143710 78128649 78128590 78116185 78116185 78116162 78116219 78116254 78116158 78116114 78116133 78116173 78116266 78116263 78116645 78115353 78115305 78111101 78105843 78105925 78105975 78106040 781...
result:
ok 100071 lines
Test #16:
score: 0
Accepted
time: 3091ms
memory: 137632kb
input:
bffbcfabceeecdefceabfbccddbebbfcbbbabaacfafcfeafafeceabcdccfbdabbcecdcffcfadabddeabdaafeddebbdffaecbcbcabdffacbdcbddfbbaabedeafbecdecefdedddaaeffbacdeebeefbfbffcfddfebcbbeccedeeefdebbaacfdeffebdddbfbdcdebccacebfbfceabdebfeeedcebdedcacfaffbfcbdfccdfefdeaabbcfeaffbeffbbaabafcdefeeaacbeeaeabcfaecdaeeff...
output:
78154822 78154734 78171887 78171913 78171801 78171608 78171590 78171695 78163868 78163711 78163667 78163667 78163659 78163665 78163665 78163552 78163516 78163571 78163583 78163494 78163473 78132769 78132778 78132889 78132834 78132947 78132973 78133049 78133171 78133218 78133275 78133383 78133434 781...
result:
ok 159786 lines
Test #17:
score: 0
Accepted
time: 4289ms
memory: 137644kb
input:
abababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababab...
output:
4166429970 3396239736 4091731954 4731504642 4230620114 3559739065 4027710752 4602433682 4175152200 4515397968 3624282094 4274472032 4444972068 4249313680 3607953935 3829700174 3751295659 4047885280 3981308765 4212013653 3972434990 4553442452 3841611860 3394962402 3817107942 3808637369 4234760470 358...
result:
ok 99776 lines
Test #18:
score: 0
Accepted
time: 5867ms
memory: 137704kb
input:
feedccacafdfececfaefddafeeecfaeeeccbbededdecabdfefffbddcbefdcabdbdabceeaabecbbcdebdeeaebfbeceffebbdecaabfbbfafbccdcdddccffdfffacbdefdcacfceecfedfdefacdaeaceeaefbcbeaffbebccfbaafaeedfbeecbcefcbfaefcfdeadcbdfceedbeffebebdafdfecaabcdedadbbbfeccdaceefcdeffecfecdebdececbcbdccbcbdbddeebeeefeccbbeebbabdaaf...
output:
216837869 274005249 229345755 285303454 209810736 267191388 277216654 250324974 299229003 219896571 249404975 288210172 214242328 266722832 238783537 260711000 251984044 297644944 257669288 277114557 281503683 240639710 246035919 257756403 269465169 280110108 267858414 259784798 256665243 220883303 ...
result:
ok 100006 lines
Test #19:
score: 0
Accepted
time: 0ms
memory: 3796kb
input:
abbacac 8 1 1 7 2 5 a 1 4 6 1 1 7 2 6 b 1 2 6 1 5 7 1 1 1
output:
4 2 6 4 0 0
result:
ok 6 lines