Predicting Popularity

First, compress the problem down to what actually matters.

For user $i$, define

$$b_i = \max(a_i-ac,0)+\max(d_i-dr,0).$$

This is exactly how much current popularity $p$ the movie needs before user $i$ is willing to watch. After this, action and drama are gone. They were just a slightly fancier way of giving us thresholds.

So the process becomes:

• every user has a threshold $b_i$;
• initially $p=0$;
• while there is an unwatched user with $b_i\le p$, they watch and $p$ increases by $1$.

The Key Process

Sort the thresholds:

$$b_1\le b_2\le \dots\le b_n.$$

The process is just scanning this sorted list. If the smallest remaining threshold is too large, nobody else can watch. If it is small enough, take them.

So we can consume user $j$ iff

$$b_j\le j-1.$$

After $j-1$ people have watched, popularity is $j-1$, so the $j$-th smallest threshold must be at most that.

But sorting after every update is obviously dead on arrival: $n,m$ are huge.

Turn It Into Counts

Let

$$F(x)=\#\{i:b_i\le x\}.$$

If current popularity is $p$, then exactly $F(p)$ users have threshold at most $p$.

If $F(p)>p$, then there is still at least one unwatched suitable user, so the process continues.

If $F(p)=p$, then all users with threshold at most $p$ have already watched, and nobody else is suitable. The process stops.

Therefore the answer is the smallest $p$ such that

$$F(p)=p.$$

Why smallest? Because we start from $0$ and only move upward. If $F(0)>0$, we jump forward. If still $F(p)>p$, we continue. The first fixed point is where the chain gets stuck.

Also, if everyone watches, answer is $n$. Any threshold above $n$ can be treated as irrelevant for positions $0\dots n$, because popularity never exceeds $n$.

The Segment Tree Value

Define

$$g(x)=F(x)-x.$$

We need the first $x$ where $g(x)=0$.

Important facts:

• before the answer, $g(x)>0$;
• at the answer, $g(x)=0$;
• $g(n)=F(n)-n=0$, so a zero always exists.

Now what happens when one user's threshold changes?

Suppose old threshold is $u$ and new threshold is $v$.

Removing old $u$ decreases $F(x)$ by $1$ for every $x\ge u$. Adding new $v$ increases $F(x)$ by $1$ for every $x\ge v$.

So:

• remove old threshold: add $-1$ to range $[u,n]$ if $u\le n$;
• add new threshold: add $+1$ to range $[v,n]$ if $v\le n$.

This is screaming lazy segment tree.

Finding The First Zero

The tree stores range minimum of $g(x)$.

Because $g(x)$ is never negative on $[0,n]$, checking whether a segment minimum is $0$ is exactly checking whether that segment contains a zero. Then we descend:

• if the left child has minimum $0$, go left;
• otherwise go right.

That gives the first zero, which is the answer.

Initialization

Start with

$$g(x)=-x$$

for all $x=0,1,\dots,n$.

Then for every user threshold $b_i$:

• if $b_i\le n$, add $+1$ to range $[b_i,n]$.

After this, each position $x$ contains

$$-x + \#\{i:b_i\le x\}=F(x)-x.$$

Each query updates one threshold, does two range additions, then returns the first zero.

Complexity

There are $n+1$ segment tree positions. Each update does $O(\log n)$ range operations and one $O(\log n)$ descent.

Total complexity:

$$O((n+m)\log n)$$

with $O(n)$ memory.

That fits easily. Not even close to needing weird hacks.