fork download
copy 
  1.  
  2. import java.io.*;
  3.  
  4. public class Main {
  5.  
  6.     static class EntradaRapida {
  7.         private final BufferedInputStream flujo =
  8.             new BufferedInputStream(System.in);
  9.  
  10.         private final byte[] buffer = new byte[1 << 16];
  11.         private int indice = 0;
  12.         private int limite = 0;
  13.  
  14.         private int leer() throws IOException {
  15.             if (indice == limite) {
  16.                 limite = flujo.read(buffer);
  17.                 indice = 0;
  18.  
  19.                 if (limite <= 0) return -1;
  20.             }
  21.  
  22.             return buffer[indice++];
  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 numero = 0;
  34.  
  35.             while (caracter > 32) {
  36.                 numero = numero * 10 + caracter - '0';
  37.                 caracter = leer();
  38.             }
  39.  
  40.             return numero;
  41.         }
  42.  
  43.         String leerCadena() throws IOException {
  44.             StringBuilder texto = new StringBuilder();
  45.             int caracter;
  46.  
  47.             do {
  48.                 caracter = leer();
  49.                 if (caracter == -1) return null;
  50.             } while (caracter <= 32);
  51.  
  52.             while (caracter > 32) {
  53.                 texto.append((char) caracter);
  54.                 caracter = leer();
  55.             }
  56.  
  57.             return texto.toString();
  58.         }
  59.  
  60.         char leerLetra() throws IOException {
  61.             int caracter;
  62.  
  63.             do {
  64.                 caracter = leer();
  65.             } while (caracter <= 32 && caracter != -1);
  66.  
  67.             return (char) caracter;
  68.         }
  69.     }
  70.  
  71.     static class ArbolSegmentos {
  72.         private final int base;
  73.         private final int[] arbol;
  74.  
  75.         ArbolSegmentos(char[] cadena) {
  76.             int tamano = cadena.length;
  77.  
  78.             int potencia = 1;
  79.  
  80.             while (potencia < tamano) {
  81.                 potencia <<= 1;
  82.             }
  83.  
  84.             base = potencia;
  85.             arbol = new int[base << 1];
  86.  
  87.             construir(cadena);
  88.         }
  89.  
  90.         private void construir(char[] cadena) {
  91.             for (int i = 0; i < cadena.length; i++) {
  92.                 arbol[base + i] = 1 << (cadena[i] - 'a');
  93.             }
  94.  
  95.             for (int i = base - 1; i > 0; i--) {
  96.                 arbol[i] = arbol[i << 1] |
  97.                            arbol[i << 1 | 1];
  98.             }
  99.         }
  100.  
  101.         void actualizar(int posicion, char letra) {
  102.             int nodo = base + posicion;
  103.  
  104.             arbol[nodo] = 1 << (letra - 'a');
  105.  
  106.             for (nodo >>= 1; nodo > 0; nodo >>= 1) {
  107.                 arbol[nodo] = arbol[nodo << 1] |
  108.                               arbol[nodo << 1 | 1];
  109.             }
  110.         }
  111.  
  112.         int consultar(int izquierda, int derecha) {
  113.             int mascara = 0;
  114.  
  115.             izquierda += base;
  116.             derecha += base + 1;
  117.  
  118.             while (izquierda < derecha) {
  119.  
  120.                 if ((izquierda & 1) != 0) {
  121.                     mascara |= arbol[izquierda++];
  122.                 }
  123.  
  124.                 if ((derecha & 1) != 0) {
  125.                     mascara |= arbol[--derecha];
  126.                 }
  127.  
  128.                 izquierda >>= 1;
  129.                 derecha >>= 1;
  130.             }
  131.  
  132.             return Integer.bitCount(mascara);
  133.         }
  134.     }
  135.  
  136.     static void resolver(EntradaRapida lector) throws IOException {
  137.  
  138.         String entrada = lector.leerCadena();
  139.  
  140.         if (entrada == null) return;
  141.  
  142.         char[] cadena = entrada.toCharArray();
  143.  
  144.         int cantConsultas = lector.leerEntero();
  145.  
  146.         ArbolSegmentos arbol = new ArbolSegmentos(cadena);
  147.  
  148.         StringBuilder resultado = new StringBuilder();
  149.  
  150.         for (int i = 0; i < cantConsultas; i++) {
  151.  
  152.             int tipo = lector.leerEntero();
  153.  
  154.             if (tipo == 1) {
  155.  
  156.                 int posicion = lector.leerEntero() - 1;
  157.                 char letra = lector.leerLetra();
  158.  
  159.                 if (cadena[posicion] != letra) {
  160.                     cadena[posicion] = letra;
  161.                     arbol.actualizar(posicion, letra);
  162.                 }
  163.  
  164.             } else {
  165.  
  166.                 int izquierda = lector.leerEntero() - 1;
  167.                 int derecha = lector.leerEntero() - 1;
  168.  
  169.                 resultado.append(
  170.                     arbol.consultar(izquierda, derecha)
  171.                 ).append('\n');
  172.             }
  173.         }
  174.  
  175.         System.out.print(resultado);
  176.     }
  177.  
  178.     public static void main(String[] args) throws IOException {
  179.         resolver(new EntradaRapida());
  180.     }
  181. }
Success #stdin #stdout 0.07s 54756KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/cJU5tV
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!