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++];
  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 valor = 0;
  34.  
  35.             while (caracter > 32) {
  36.                 valor = valor * 10 + caracter - '0';
  37.                 caracter = leer();
  38.             }
  39.  
  40.             return valor;
  41.         }
  42.  
  43.         String leerCadena() throws IOException {
  44.             StringBuilder cadenaLeida = 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.                 cadenaLeida.append((char) caracter);
  54.                 caracter = leer();
  55.             }
  56.  
  57.             return cadenaLeida.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 inicioArbol;
  73.         private final int[] segmentos;
  74.  
  75.         ArbolSegmentos(char[] letras) {
  76.             int longitud = letras.length;
  77.             int capacidad = 1;
  78.  
  79.             while (capacidad < longitud) {
  80.                 capacidad <<= 1;
  81.             }
  82.  
  83.             inicioArbol = capacidad;
  84.             segmentos = new int[inicioArbol << 1];
  85.  
  86.             construir(letras);
  87.         }
  88.  
  89.         private void construir(char[] letras) {
  90.             for (int i = 0; i < letras.length; i++) {
  91.                 segmentos[inicioArbol + i] =
  92.                     1 << (letras[i] - 'a');
  93.             }
  94.  
  95.             for (int actual = inicioArbol - 1; actual > 0; actual--) {
  96.                 segmentos[actual] = segmentos[actual << 1] |
  97.                                     segmentos[actual << 1 | 1];
  98.             }
  99.         }
  100.  
  101.         void actualizar(int indice, char nuevoCaracter) {
  102.             int actual = inicioArbol + indice;
  103.  
  104.             segmentos[actual] = 1 << (nuevoCaracter - 'a');
  105.  
  106.             for (actual >>= 1; actual > 0; actual >>= 1) {
  107.                 segmentos[actual] = segmentos[actual << 1] |
  108.                                     segmentos[actual << 1 | 1];
  109.             }
  110.         }
  111.  
  112.         int consultar(int inicio, int fin) {
  113.             int letrasPresentes = 0;
  114.  
  115.             inicio += inicioArbol;
  116.             fin += inicioArbol + 1;
  117.  
  118.             while (inicio < fin) {
  119.  
  120.                 if ((inicio & 1) != 0) {
  121.                     letrasPresentes |= segmentos[inicio++];
  122.                 }
  123.  
  124.                 if ((fin & 1) != 0) {
  125.                     letrasPresentes |= segmentos[--fin];
  126.                 }
  127.  
  128.                 inicio >>= 1;
  129.                 fin >>= 1;
  130.             }
  131.  
  132.             return Integer.bitCount(letrasPresentes);
  133.         }
  134.     }
  135.  
  136.     static void resolver(EntradaRapida entrada) throws IOException {
  137.  
  138.         String cadenaInicial = entrada.leerCadena();
  139.  
  140.         if (cadenaInicial == null) return;
  141.  
  142.         char[] caracteres = cadenaInicial.toCharArray();
  143.  
  144.         int totalConsultas = entrada.leerEntero();
  145.  
  146.         ArbolSegmentos estructura = new ArbolSegmentos(caracteres);
  147.  
  148.         StringBuilder salida = new StringBuilder();
  149.  
  150.         for (int consulta = 0; consulta < totalConsultas; consulta++) {
  151.  
  152.             int operacion = entrada.leerEntero();
  153.  
  154.             if (operacion == 1) {
  155.  
  156.                 int indice = entrada.leerEntero() - 1;
  157.                 char nuevoCaracter = entrada.leerLetra();
  158.  
  159.                 if (caracteres[indice] != nuevoCaracter) {
  160.                     caracteres[indice] = nuevoCaracter;
  161.                     estructura.actualizar(indice, nuevoCaracter);
  162.                 }
  163.  
  164.             } else {
  165.  
  166.                 int inicio = entrada.leerEntero() - 1;
  167.                 int fin = entrada.leerEntero() - 1;
  168.  
  169.                 salida.append(
  170.                     estructura.consultar(inicio, fin)
  171.                 ).append('\n');
  172.             }
  173.         }
  174.  
  175.         System.out.print(salida);
  176.     }
  177.  
  178.     public static void main(String[] args) throws IOException {
  179.         resolver(new EntradaRapida());
  180.     }
  181. }
Success #stdin #stdout 0.07s 52708KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/62Icaj
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!