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