每日一题5.22

Fengyj

https://codeforces.com/gym/105911/problem/E


南昌邀请赛金牌题，李悦他们做出来这道才金牌

XinyuLin

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 3e5 + 5;

int n, k, q;
string s;

// ---------- 一次性求出每个前缀的 26 维向量 ----------
using Vec = array<int, 26>;
Vec pref[MAXN];            // pref[i] = Σ s[0..i-1]  % k
int id[MAXN];              // 每个前缀向量离散后的编号

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> k >> q;
    cin >> s;

    vector<Vec> all;   all.reserve(n + 1);
    pref[0].fill(0);
    all.push_back(pref[0]);

    for (int i = 0; i < n; ++i) {
        pref[i + 1] = pref[i];
        int t = s[i] - 'a';
        pref[i + 1][t] += 1;
        if (pref[i + 1][t] >= k) pref[i + 1][t] -= k;
        all.push_back(pref[i + 1]);
    }

    /* ---- 离散化 ---- */
    vector<int> ord(all.size());
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int a, int b) { return all[a] < all[b]; });

    int curID = 0;
    Vec last = all[ord[0]];
    auto same = [&](const Vec& A, const Vec& B) {
        for (int i = 0; i < 26; ++i) if (A[i] != B[i]) return false;
        return true;
    };

    id[ord[0]] = curID;
    for (size_t i = 1; i < ord.size(); ++i) {
        if (!same(all[ord[i]], last)) { ++curID; last = all[ord[i]]; }
        id[ord[i]] = curID;
    }
    const int kinds = curID + 1;          // 离散后种类数

    // ---------- 读取查询 ----------
    struct Q { int l, r, idx; };
    vector<Q> qs(q);
    for (int i = 0; i < q; ++i) {
        cin >> qs[i].l >> qs[i].r;
        qs[i].l--;            // 变成前缀下标 [l-1, r]
        qs[i].idx = i;
    }

    /* ---- Mo 排序 ---- */
    int S = max(1, int(n / sqrt(q)));     // 建议 700~1000 都可
    sort(qs.begin(), qs.end(), [&](const Q& a, const Q& b) {
        int blockA = a.l / S, blockB = b.l / S;
        if (blockA != blockB) return blockA < blockB;
        return (blockA & 1) ? a.r < b.r : a.r > b.r;
    });

    // ---------- Mo 主循环 ----------
    vector<long long> cnt(kinds, 0);
    vector<long long> ans(q);
    long long cur = 0;
    int L = 0, R = -1;

    auto add = [&](int pos) {
        long long c = cnt[id[pos]];
        cur += c;
        ++cnt[id[pos]];
    };
    auto remove = [&](int pos) {
        --cnt[id[pos]];
        long long c = cnt[id[pos]];
        cur -= c;
    };

    for (const auto& qu : qs) {
        int l = qu.l, r = qu.r;
        while (L > l) add(--L);
        while (R < r) add(++R);
        while (L < l) remove(L++);
        while (R > r) remove(R--);
        ans[qu.idx] = cur;
    }

    for (auto x : ans) cout << x << '\n';
    return 0;
}

495684945

[C++] 纯文本查看 复制代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int>PII;

void solve(){
	int n,k,q;
	cin>>n>>k>>q;
	string str;
	cin>>str;
	str=" "+str;
	int lim=sqrt(n),idx=0,res=0;
	vector<array<int,4>>que(q+10);
	vector<int>mmap(n+10),ans(q+10),cnt(n+10);
	map<vector<int>,int>mp;
	vector pre(n+10,vector<int>(26));
	for(int i=1;i<=n;i++){
		for(int j=0;j<=25;j++){
			if(j==str[i]-'a'){
				pre[i][j]=(pre[i-1][j]+1)%k;
			}else pre[i][j]=pre[i-1][j];
		}
	}
	for(int i=0;i<=n;i++){
		if(!mp.count(pre[i])){
			mp[pre[i]]=idx++;
		}
		mmap[i]=mp[pre[i]];
	}
	for(int i=1;i<=q;i++){
		int x,y;
		cin>>x>>y;
		que[i]=array<int,4>{x-1,y,i,(x-1)/lim};
	}
	sort(que.begin()+1,que.begin()+1+q,[](array<int,4>&a,array<int,4>&b){
		if(a[3]!=b[3])return a[3]<b[3];
		return a[1]<b[1];
	});
	auto add=[&](int x){
		int &t=cnt[mmap[x]];
		res=res+t;
		t++;
	};
	auto del=[&](int x){
		int &t=cnt[mmap[x]];
		res=res-(t-1);
		t--;
	};
	for(int i=1,l=1,r=0;i<=q;i++){
		int l2=que[i][0],r2=que[i][1];
		while(r<r2)add(++r);
		while(r>r2)del(r--);
		while(l<l2)del(l++);
		while(l>l2)add(--l);
		ans[que[i][2]]=res;
	}
	for(int i=1;i<=q;i++)cout<<ans[i]<<endl;
}

signed main(){
	int t=1;ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
//	cin>>t;
	while(t--)solve();
	return 0;
}

Fengyj

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
#define int long long
template <class S, class T>
using omap = __gnu_pbds::gp_hash_table<S, T>;

struct ArrHash
{
    size_t operator()(const array<int, 26> &a) const noexcept
    {
        uint64_t h = 0;
   
        for (auto x : a)
        {
            h = h * 1000003ULL ^ (uint64_t(x) + 0x9e3779b97f4a7c15ULL);
        }
        return size_t(h);
    }
};

void solve()
{
    int n, k, q;
    cin >> n >> k >> q;

    unordered_map<array<int, 26>, int,ArrHash> mp;

    string s;
    cin >> s;
    s = " " + s;
    vector<int> pre(n + 1), id(n + 1);

    array<int, 26> key{};
    mp[key] = 0;
    id[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        pre[i] = pre[i - 1] + s[i] - 'a';
        key[s[i] - 'a'] = (key[s[i] - 'a'] + 1) % k;

        auto it = mp.find(key);
        if (it == mp.end())
        {
            id[i] = mp.size();
            mp.insert({key, id[i]});
        }
        else
        {
            id[i] = it->second;
        }
    }
    vector<array<int, 3>> query(q);
    for (int i = 0; i < q; i++)
    {
        cin >> query[i][0] >> query[i][1];
        query[i][0]--;
        query[i][2] = i;
    }

    int block = max(1ll, (int)(n / sqrt(q)));

    sort(query.begin(), query.end(), [&](array<int, 3> a, array<int, 3> b)
         { int blk1 = a[0] / block;
        int blk2 = b[0] / block;
        if (blk1!=blk2)
            return blk1 < blk2;
        return blk1 & 1 ? a[1] < b[1] : a[1] > b[1]; });

    vector<int> f(mp.size()+1);
    int L = 0, R = -1;
    int ans = 0;
    auto add = [&](int x)
    {
        int v = id[x];
        ans += f[v];
        f[v]++;
    };

    auto del = [&](int x)
    {
        int v=id[x];
        f[v]--;
        ans -= f[v];
    };
    vector<int> res(q);
    for(auto [l,r,idx]:query){
        while(L>l)
            add(--L);
        while(L<l)
            del(L++);
        while(R>r)
            del(R--);
        while(R<r)
            add(++R);
        res[idx] = ans;
    }
    for(auto i:res)
        cout << i << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}