fork download
copy 
  1.  
  2. import java.io.*;
  3.  
  4. public class Main {
  5.  
  6.     static class EntradaRapida {
  7.         private final BufferedInputStream entrada =
  8.             new BufferedInputStream(System.in);
  9.  
  10.         private final byte[] datos = new byte[1 << 16];
  11.         private int pos = 0;
  12.         private int longitud = 0;
  13.  
  14.         private int leer() throws IOException {
  15.             if (pos >= longitud) {
  16.                 longitud = entrada.read(datos);
  17.                 pos = 0;
  18.  
  19.                 if (longitud <= 0) return -1;
  20.             }
  21.  
  22.             return datos[pos++] & 255;
  23.         }
  24.  
  25.         int leerEntero() throws IOException {
  26.             int caracter;
  27.  
  28.             do {
  29.                 caracter = leer();
  30.                 if (caracter == -1) return -1;
  31.             } while (caracter <= 32);
  32.  
  33.             int signo = 1;
  34.  
  35.             if (caracter == '-') {
  36.                 signo = -1;
  37.                 caracter = leer();
  38.             }
  39.  
  40.             int valor = 0;
  41.  
  42.             while (caracter > 32 && caracter != -1) {
  43.                 valor = valor * 10 + caracter - '0';
  44.                 caracter = leer();
  45.             }
  46.  
  47.             return valor * signo;
  48.         }
  49.  
  50.         String leerCadena() throws IOException {
  51.             StringBuilder resultado = new StringBuilder();
  52.             int caracter;
  53.  
  54.             do {
  55.                 caracter = leer();
  56.                 if (caracter == -1) return null;
  57.             } while (caracter <= 32);
  58.  
  59.             while (caracter > 32 && caracter != -1) {
  60.                 resultado.append((char) caracter);
  61.                 caracter = leer();
  62.             }
  63.  
  64.             return resultado.toString();
  65.         }
  66.  
  67.         char leerLetra() throws IOException {
  68.             int caracter;
  69.  
  70.             do {
  71.                 caracter = leer();
  72.             } while (caracter != -1 && caracter <= 32);
  73.  
  74.             return caracter == -1 ? '\0' : (char) caracter;
  75.         }
  76.     }
  77.  
  78.     static class ArbolSegmentos {
  79.         private final int inicioArbol;
  80.         private final int[] segmentos;
  81.         private final int longitud;
  82.  
  83.         ArbolSegmentos(char[] letras) {
  84.             longitud = letras.length;
  85.  
  86.             int capacidad = 1;
  87.  
  88.             while (capacidad < longitud) {
  89.                 capacidad <<= 1;
  90.             }
  91.  
  92.             inicioArbol = capacidad;
  93.             segmentos = new int[inicioArbol << 1];
  94.  
  95.             construir(letras);
  96.         }
  97.  
  98.         private int mascara(char caracter) {
  99.             if (caracter < 'a' || caracter > 'z') {
  100.                 return 0;
  101.             }
  102.  
  103.             return 1 << (caracter - 'a');
  104.         }
  105.  
  106.         private void construir(char[] letras) {
  107.             for (int i = 0; i < longitud; i++) {
  108.                 segmentos[inicioArbol + i] = mascara(letras[i]);
  109.             }
  110.  
  111.             for (int i = inicioArbol - 1; i > 0; i--) {
  112.                 segmentos[i] =
  113.                     segmentos[i << 1] |
  114.                     segmentos[i << 1 | 1];
  115.             }
  116.         }
  117.  
  118.         void actualizar(int indice, char nuevoCaracter) {
  119.             if (indice < 0 || indice >= longitud) return;
  120.  
  121.             int actual = inicioArbol + indice;
  122.  
  123.             segmentos[actual] = mascara(nuevoCaracter);
  124.  
  125.             actual >>= 1;
  126.  
  127.             while (actual > 0) {
  128.                 segmentos[actual] =
  129.                     segmentos[actual << 1] |
  130.                     segmentos[actual << 1 | 1];
  131.  
  132.                 actual >>= 1;
  133.             }
  134.         }
  135.  
  136.         int consultar(int inicio, int fin) {
  137.             if (inicio < 0 || fin >= longitud || inicio > fin) {
  138.                 return 0;
  139.             }
  140.  
  141.             inicio += inicioArbol;
  142.             fin += inicioArbol + 1;
  143.  
  144.             int resultado = 0;
  145.  
  146.             while (inicio < fin) {
  147.                 if ((inicio & 1) != 0) {
  148.                     resultado |= segmentos[inicio++];
  149.                 }
  150.  
  151.                 if ((fin & 1) != 0) {
  152.                     resultado |= segmentos[--fin];
  153.                 }
  154.  
  155.                 inicio >>= 1;
  156.                 fin >>= 1;
  157.             }
  158.  
  159.             return Integer.bitCount(resultado);
  160.         }
  161.     }
  162.  
  163.     static void resolver(EntradaRapida entrada) throws IOException {
  164.         String cadena = entrada.leerCadena();
  165.  
  166.         if (cadena == null) return;
  167.  
  168.         char[] caracteres = cadena.toCharArray();
  169.  
  170.         int totalConsultas = entrada.leerEntero();
  171.  
  172.         if (totalConsultas < 0) return;
  173.  
  174.         ArbolSegmentos arbol = new ArbolSegmentos(caracteres);
  175.  
  176.         StringBuilder salida = new StringBuilder();
  177.  
  178.         for (int i = 0; i < totalConsultas; i++) {
  179.             int operacion = entrada.leerEntero();
  180.  
  181.             if (operacion == -1) break;
  182.  
  183.             if (operacion == 1) {
  184.                 int indice = entrada.leerEntero() - 1;
  185.                 char nuevoCaracter = entrada.leerLetra();
  186.  
  187.                 if (indice >= 0 &&
  188.                     indice < caracteres.length &&
  189.                     nuevoCaracter >= 'a' &&
  190.                     nuevoCaracter <= 'z') {
  191.  
  192.                     caracteres[indice] = nuevoCaracter;
  193.                     arbol.actualizar(indice, nuevoCaracter);
  194.                 }
  195.  
  196.             } else if (operacion == 2) {
  197.                 int inicio = entrada.leerEntero() - 1;
  198.                 int fin = entrada.leerEntero() - 1;
  199.  
  200.                 salida.append(
  201.                     arbol.consultar(inicio, fin)
  202.                 ).append('\n');
  203.             }
  204.         }
  205.  
  206.         System.out.print(salida);
  207.     }
  208.  
  209.     public static void main(String[] args) throws IOException {
  210.         resolver(new EntradaRapida());
  211.     }
  212. }
  213.  
Success #stdin #stdout 0.06s 52704KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/IIzZmG
language:
Java (12.0.1)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!