首页 > 代码库 > CodeChef January Challenge Queries on the StringSolved

CodeChef January Challenge Queries on the StringSolved

2024-10-23 17:20:01   210人阅读

只能说太弱了。。。 别人眼中的水题。。 我到现在还不知道能不能写出~~

维护前缀和并且应用同余定理： (sum[r] - sum[l-1])%3 == 0 -> (sum[r]%3 - sum[l-1]%3)%3 == 0 -> sum[r]%3 == sum[l-1]%3

线段树维护前缀和中0,1,2的个数即可；

 

发来kuangbin巨的代码；

#include <stdio.h>#include <string.h>#include <iostream>#include <algorithm>#include <vector>#include <queue>#include <set>#include <map>#include <string>#include <math.h>#include <stdlib.h>#include <time.h>using namespace std;const int MAXN = 100010;struct Node{int l,r;int c[3];int add;}segTree[MAXN<<2];void Update_Add(int i,int val){int cc[3];for(int j = 0;j < 3;j++)cc[j] = segTree[i].c[(j-val+3)%3];for(int j = 0;j < 3;j++)segTree[i].c[j] = cc[j];segTree[i].add += val;segTree[i].add %= 3;}void push_up(int i){for(int j = 0;j < 3;j++)segTree[i].c[j] = segTree[i<<1].c[j]+segTree[(i<<1)|1].c[j];}void push_down(int i){if(segTree[i].add){Update_Add(i<<1,segTree[i].add);Update_Add((i<<1)|1,segTree[i].add);segTree[i].add = 0;}}int a[MAXN],b[MAXN];void build(int i,int l,int r){segTree[i].l = l;segTree[i].r = r;for(int j = 0;j < 3;j++)segTree[i].c[j] = 0;segTree[i].add = 0;if(l == r){segTree[i].c[b[l]]++;return;}int mid = (l+r)/2;build(i<<1,l,mid);build((i<<1)|1,mid+1,r);push_up(i);}void update(int i,int l,int r,int val){if(val == 0)return;if(segTree[i].l == l && segTree[i].r == r){Update_Add(i,val);return;}push_down(i);int mid = (segTree[i].l + segTree[i].r)/2;if(r <= mid)update(i<<1,l,r,val);else if(l > mid)update((i<<1)|1,l,r,val);else {update(i<<1,l,mid,val);update((i<<1)|1,mid+1,r,val);}push_up(i);}int query(int i,int l,int r,int c0){if(segTree[i].l == l && segTree[i].r == r)return segTree[i].c[c0];push_down(i);int mid = (segTree[i].l + segTree[i].r)/2;if(r <= mid)return query(i<<1,l,r,c0);else if(l > mid)return query((i<<1)|1,l,r,c0);else {return query(i<<1,l,mid,c0)+query((i<<1)|1,mid+1,r,c0);}}char str[MAXN];int main(){int n,m;while(scanf("%d%d",&n,&m) == 2){scanf("%s",str);b[0] = 0;n++;a[1] = b[1] = 0;for(int i = 2;i <= n;i++){a[i] = str[i-2]-‘0‘;b[i] = (b[i-1]+a[i])%3;}build(1,1,n);while(m--){int op;scanf("%d",&op);if(op == 1){int x,y;scanf("%d%d",&x,&y);x++;update(1,x,n,(y-a[x]+3)%3);a[x] = y;}else {int x,y;scanf("%d%d",&x,&y);y++;long long ans = 0;int tmp = query(1,x,y,0);ans += (long long)tmp*(tmp-1)/2;tmp = query(1,x,y,1);ans += (long long)tmp*(tmp-1)/2;tmp = query(1,x,y,2);ans += (long long)tmp*(tmp-1)/2;cout<<ans<<endl;}}}}

 

CodeChef January Challenge Queries on the StringSolved


联系
我们