Advertisement
Guest User

Untitled

a guest
May 25th, 2018
69
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.34 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <string>
  5. using namespace std;
  6.  
  7. struct punkt{
  8.     int pocz, kon;
  9.     int suma;
  10. };
  11.  
  12.  
  13. vector < punkt > drzewo;
  14. int wlk = 1;
  15. void Dodaj(int poz, int wart1, int wart2){
  16.     poz+=wlk;
  17.     drzewo[poz].kon += wart1;
  18.     drzewo[poz].pocz += wart2;
  19.     poz/=2;
  20.     while(poz>0){
  21.         drzewo[poz].pocz = drzewo[poz*2].pocz;
  22.         drzewo[poz].kon = drzewo[poz*2+1].kon;
  23.         drzewo[poz].suma += drzewo[poz].pocz * drzewo[poz].kon + drzewo[poz*2].suma + drzewo[poz*2 + 1].suma;
  24.         drzewo[poz].pocz += drzewo[poz*2+1].pocz;
  25.         drzewo[poz].kon += drzewo[poz*2].kon;
  26.         poz/=2;
  27.     }
  28. }
  29.  
  30. void Zmien(int poz){
  31.     poz+=wlk;
  32.     if (drzewo[poz].pocz == 1){
  33.         Dodaj(poz-wlk, 1, -1);
  34.     }
  35.     else{
  36.         Dodaj(poz-wlk, -1, 1);
  37.     }
  38. }
  39.  
  40. int main(){
  41.     int N;
  42.     int Q;
  43.     cin >> N >> Q;
  44.  
  45.     while(wlk <= N){wlk*=2;}
  46.     drzewo.resize(wlk*2);
  47.     string slowo;
  48.     cin >> slowo;
  49.     for (int i = 0; i < N; i++){
  50.         if(slowo[i] == 'P'){
  51.             Dodaj(i, 0, 1);
  52.         }
  53.         else{
  54.             Dodaj(i, 1, 0);
  55.         }
  56.     }
  57.     cout << drzewo[1].suma << "\n";
  58.     for (int i = 0; i < Q; i++){
  59.         int poz;
  60.         cin >> poz;
  61.         poz--;
  62.         Zmien(poz);
  63.         cout << drzewo[1].suma << "\n";
  64.     }
  65. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement