Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
- char *str(char *dest, char *src, int m, int n)
- {
- int i;
- char *temp = dest;
- for(i = 0; i<n;++i) dest[m + i] = src[i];
- return temp;
- }
- /*int opr(char p)
- {
- int i, k = 1;
- for(i = 0; i < p - 97; ++i) k*= 2;
- return k;
- }*/
- void build(int *t, char *a, int v, int l, int r)
- {
- if(l == r) t[v] = 1<< (a[l] - 97);
- else {
- int m = (l + r)/2;
- build(t, a, v * 2, l, m);
- build(t, a, v * 2 + 1 , m + 1, r);
- t[v] = (t[v * 2]) ^ (t[v * 2 + 1]);
- }
- }
- void SegmentTree_Build(char *a, int *t, int n)
- {
- int i;
- //for(i = 0; i < 4 * n; ++i) t[i] = 0;
- build(t, a, 1, 0, n - 1);
- }
- int query(int *t, int l, int r, int v, int a, int b)
- {
- if(l == a && r == b) return t[v];
- else{
- int m = (a + b)/2;
- if(r <= m) return query(t, l, r, v * 2, a, m);
- else {
- if (l > m) return query(t , l , r, v * 2 + 1, m + 1, b);
- else return query(t, l, m, v * 2, a, m) ^ query(t, m + 1, r, v * 2 + 1, m + 1, b);
- }
- }
- }
- int SegmentTree_Query(int *t, int n, int l, int r)
- {
- int k = query(t, l, r, 1, 0, n - 1);
- return k;
- }
- void update(int *t, int i, char d, int v, int a, int b)
- {
- if(a == b) t[v] = 1<<(d - 97);
- else{
- int m = (a + b)/2;
- if(i <= m) update(t, i, d, v * 2, a, m);
- else update(t, i, d, v * 2 + 1, m + 1, b);
- t[v] = t[v * 2] ^ t[v * 2 + 1];
- }
- }
- void SegmentTree_Update(int *t, int i, char *d, int m, int n)
- {
- int j;
- for(j = 0; j < m;++j, ++i) update(t, i, d[j], 1, 0, n - 1);
- }
- int main(int argc, char **argv)
- {
- int i, n, m, r, l, k;
- char p[4];
- p[3] = 0;
- char *b = (char*)malloc(1000001 * sizeof(char));
- char *a = (char*)malloc(1000001 * sizeof(char));
- gets(a);
- n = strnlen(a, 1000001);
- int *t = (int*)malloc(4 * n * sizeof(int));
- int log2n = -1;
- for(;1<<(log2n + 1) <= n; ++log2n);
- //t = (int*)malloc(4 * n * sizeof(int));
- SegmentTree_Build(a,t,n);
- //free(a);
- scanf("%d", &m);
- for(i = 0; i < m;++i){
- scanf("%s", p);
- if(p[0] == 'H'){
- scanf("%d%d", &l, &r);
- k = SegmentTree_Query(t, n, l, r);
- //printf("%d,k", k);
- if(((k - 1) & k) == 0 || k == 0) printf("YES\n");
- else printf("NO\n");
- } else {
- scanf("%d ", &l);
- gets(b);
- r = strnlen(b, 1000001);
- a = str(a, b, l, r);
- if(n < log2n * r) SegmentTree_Update(t, l, b, r, n);
- else SegmentTree_Build(a,t, n);
- //printf("%d %d\n", r, l);
- //a = str(a, b, l, r);
- //SegmentTree_Update(t, l, b, r, n);
- }
- }
- free(b);
- free(a);
- free(t);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement