Дшка интернет тура ВКОШП 2017-2018

Решал эту задачу. Мое решение такое:
Если i-тый человек смотрит влево, то бинарим такое j (j < i), что последовательность a_j ...a_{i-1} невозрастающая и a_j - максимальное
Иначе делаем то же самое на суффиксе
Для того, чтобы быстро проверять невозрастающая ли последовательность, можно использовать количество инверсий(посчитать количество инверсий в реверснутом массиве в отрезке [n-r+1, n-l+1] и если результат 0, то последовательность невозрастающая). А теперь вопрос - как быстро посчитать количество инверсий на отрезке за logn если n - не перестановка? (в инете нашел только про ДО и разделяй и властвуй)?

Будет ли такое работать и есть ли решение проще?:thinking:

2 симпатии

@Zhabka

1 симпатия

:open_mouth::hushed::astonished::thinking::thinking:

2 симпатии

Немного не понял твою идею, однако я решил более проще.

Решение

Будем хранить вектора L и R для тех солдат, которые смотрят либо в левую, либо в правую сторону соответственно.
Решим для L.
Вектор L мы будем заполнять начиная с начала. Несмотря на то, в какую сторону смотрит солдат, мы будем заносить его в наш вектор. Так как более высокие солдаты будут “перекрывать” более низких, то мы будем удалять их из вектора с помощью pop_back(). Если солдат смотрит в сторону L, то мы передаем ему как ответ размер вектора L.
Практически тоже самое пишем и для вектора R.

const int N = (int) 1e5;
int a[N + 100];
int ans[N + 100];
void solve(){
   int n;
   cin >> n;
   for(int i = 0; i < n; i++){
   		cin >> a[i];
   }
   vector<int> l, r;
   string s;
   cin >> s;
   for(int i = 0; i < n; i++){
   		if(s[i] == 'L') ans[i] = l.size();
   		while(true){
   			if(l.size() == 0) break;
   			if(l.back() >= a[i]) break;
   			l.pop_back();
   		}
   		l.pb(a[i]);
   }
   for(int i = n - 1; i >= 0; i--){
   		if(s[i] == 'R') ans[i] = r.size();
   		while(true){
   			if(r.size() == 0) break;
   			if(r.back() >= a[i]) break;
   			r.pop_back();
   		}
   		r.pb(a[i]);
   }
   for(int i = 0; i < n; i++){
   		cout << ans[i] << " ";
   }
} 
5 симпатий

Я понял твою идею, но она во-первых неправильная, потому что в задаче по сути спрашивают количество различных префикс/суффикс максимумов начиная с позиции i, и твоим методом это посчитать нельзя, ты скорее всего не так понял задачу, а во-вторых то, что ты описываешь теоретически работает, но на деле ультра непрактично. Если надо проверить, что последовательность невозрастает, то можно использовать простые префикс суммы, как именно это делать можешь подумать, если не поймёшь, то я расскажу. А так обратись к решению @shkhn.

2 симпатии