Advertisement
sidjha57

seg_new

Jun 26th, 2022
762
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.84 KB | None
  1. //Siddharth Jha
  2.  
  3. #include<bits/stdc++.h>
  4. //#include<ext/pb_ds/assoc_container.hpp>
  5. //#include<ext/pb_ds/tree_policy.hpp>
  6. //#include <ext/pb_ds/trie_policy.hpp>
  7. //using namespace __gnu_pbds;
  8. using namespace std;
  9. //typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
  10. //typedef trie<string,null_type,trie_string_access_traits<>,pat_trie_tag,trie_prefix_search_node_update> pbtrie;
  11.  
  12. #define ll                       long long int
  13. #define mod                      1000000007
  14. #define inf                      1e18
  15. #define pb                       push_back
  16. #define vi                       vector<ll>
  17. #define vs                       vector<string>
  18. #define pii                      pair<ll,ll>
  19. #define ump                      unordered_map
  20. #define mp                       make_pair
  21. #define pq_max                   priority_queue<ll>
  22. #define pq_min                   priority_queue<ll,vi,greater<ll> >
  23. #define all(n)                   n.begin(),n.end()
  24. #define ff                       first
  25. #define ss                       second
  26. #define mid(l,r)                 (l+(r-l)/2)
  27. #define bitc(n)                  __builtin_popcount(n)
  28. #define SET(a)                   memset( a, -1, sizeof a )
  29. #define CLR(a)                   memset( a,  0, sizeof a )
  30. #define Pi                       3.141592653589793
  31. #define loop(x,start,end)        for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
  32. #define _fast                    ios_base::sync_with_stdio(0);  cin.tie(0); cout.tie(0);
  33. #define iter(container,it)       for(__typeof(container.begin()) it = container.begin(); it != container.end(); it++)
  34. #define log(args...)             {string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
  35. #define logarr(arr,a,b)          for(int z=(a);z<=(b);z++) cout<<(arr[z])<<" ";cout<<endl;
  36. template <typename T> T          gcd(T a, T b){if(a%b) return gcd(b,a%b);return b;}
  37. template <typename T> T          lcm(T a, T b){return (a*(b/gcd(a,b)));}
  38. vs tokenizer(string str,char ch) {std::istringstream var((str)); vs v; string t; while(getline((var), t, (ch))) {v.pb(t);} return v;}
  39.  
  40. void err(istream_iterator<string> it) {}
  41. template<typename T, typename... Args>
  42. void err(istream_iterator<string> it, T a, Args... args) {
  43. cout << *it << " = " << a << endl;
  44. err(++it, args...);
  45. }
  46. // 0 based indexing
  47. struct segtree {
  48.  
  49.     vector<int> seg;
  50.     int size;
  51.  
  52.     void init(int n) {
  53.         size = 1;
  54.         while (n > size) size *= 2;
  55.         seg.assign(2*size , 0ll);
  56.     }
  57.  
  58.     void set (int i, int v,int x, int lx, int rx) {
  59.         if ((rx-lx) == 1) {
  60.             seg[x] += v;
  61.             return;
  62.         }
  63.  
  64.         ll m = mid(lx,rx);
  65.         if (i < m) {
  66.             set (i, v, 2 * x + 1, lx, m);
  67.         } else {
  68.             set (i, v, 2 * x + 2, m, rx);
  69.         }
  70.  
  71.         seg[x] = seg[2 * x + 1] + seg[2*x + 2];
  72.     }
  73.  
  74.     void set (int i, int v) {
  75.         set(i, v, 0, 0, size);
  76.     }
  77.     void build (vector<int>& a,int x, int lx, int rx) {
  78.         if ((rx-lx) == 1) {
  79.             if (lx < a.size()) {
  80.                 seg[x] = a[lx];
  81.             }
  82.             return;
  83.         }
  84.         int m = mid(lx,rx);
  85.         build (a, 2 * x + 1, lx, m);
  86.         build (a, 2 * x + 2, m, rx);
  87.         seg[x] = seg[2* x + 1] + seg[2* x + 2];
  88.     }
  89.     void build (vector<int>& a) {
  90.         build(a,0,0,size);
  91.     }
  92.    
  93.     // l to r-1
  94.     int sum (int l, int r, int x, int lx, int rx) {
  95.         if (lx >= r || l >= rx) return 0;
  96.         if (lx >= l && rx <= r) return seg[x];
  97.        
  98.         int m =  mid(lx,rx);
  99.         int s1 = sum (l, r, 2 * x + 1, lx, m);
  100.         int s2 = sum (l, r, 2 * x + 2, m, rx);
  101.         return s1+s2;
  102.     }
  103.  
  104.     int sum (int l ,int r) {
  105.         return sum (l, r, 0, 0, size);
  106.     }
  107. };
  108.  
  109. bool check (ll x, vector<vector<int>>& range, vector<segtree>& seg, string& s, vector<int>& arr) {
  110.     for (int i = 0; i <= x; i++) {
  111.         int idx = (s[arr[i]-1] - 'a'), v = -1, id = arr[i]-1;
  112.         seg[idx].set(id,v);
  113.        
  114.     }
  115.     bool flag = 1;
  116.     for (int c = 0; c < 26; c++) {
  117.         for (auto r : range) {
  118.         if (seg[c].sum(r[0]-1, r[1]) > 1) {
  119.                 flag = 0;
  120.                 break;
  121.             }
  122.         }
  123.             if (!flag) break;
  124.     }
  125.     for (int i = 0; i <= x; i++) {
  126.         int idx = (s[arr[i]-1] - 'a'), v = 1, id = arr[i]-1;
  127.         seg[idx].set(id,v);
  128.        
  129.     }
  130.     return flag;
  131. }
  132.  
  133.  
  134. void solve() {
  135.    
  136.    int n,q;
  137.    cin >> n >> q;
  138.    string s ;
  139.    cin >> s;
  140.    vector<int> arr (n);
  141.    loop (i,0,n) cin >> arr[i];
  142.    vector<vector<int>> ranges (q, vector<int>(2));
  143.    loop (i,0,q) cin >> ranges[i][0] >> ranges[i][1];
  144.    
  145. //    set<pair<int,int>> range;
  146. //    for (int i = 0; i < q; i++) {
  147. //     range.insert({ranges[i][0],ranges[i][1]});
  148. //    }
  149.  
  150.    vector<segtree> seg(26);
  151.    vector<vector<int>> freq (26, vector<int>(n,0));
  152.  
  153.    for (int i = 0; i < n; i++) {
  154.     int idx = (s[i] - 'a');
  155.     freq[idx][i]++;
  156.    }
  157.    for (int i = 0; i < 26; i++) {
  158.     seg[i].init(n);
  159.     seg[i].build(freq[i]);
  160.    }
  161.     bool flag = 1;
  162.     for (int c = 0; c < 26; c++) {
  163.         for (auto r : ranges) {
  164.             if (seg[c].sum(r[0]-1, r[1]) > 1) {
  165.                 flag = 0;
  166.                 break;
  167.             }
  168.         }
  169.         if (!flag) break;
  170.     }
  171.     if (flag) {
  172.         cout << 0 <<"\n";
  173.         return;
  174.     }
  175.     int l = 0, r = n-1, ans = n;
  176.     while (r >= l) {
  177.         int mid = (r+l)/2;
  178.         if (check(mid,ranges,seg,s,arr)) {
  179.             r = mid -1;
  180.             ans = mid + 1;
  181.         } else {
  182.             l = mid +1;
  183.         }
  184.     }
  185.     cout << ans << "\n";
  186. }
  187.  
  188. int main(int argc, char const *argv[]){
  189.     _fast
  190.  
  191.     ll t; cin >> t;
  192.     while(t--){
  193.      solve();
  194.     }
  195.   return 0;
  196. }
Advertisement
RAW Paste Data Copied
Advertisement