Spring II

It was a surprise to discover a new nest opposite the window.

Through the telescope, I scrupulously watched the doves in the nest, who were reposing restfully. Narrowly I discerned that they were a family comprised of a mother and two babies. Sighed with relief, I thought, “Finally the dove has returned, and luckily I can still see the family.” I even expected to witness the first flight of the baby doves.

I started wondering where the doves came from, as it was odd that they were inclined to construct their home here between the buildings, and after a period of cogitating, I ultimately deduced that once they might live in the decrepit houses nearby which were to be pulled down owing to the modernization and urbanization.

From this viewpoint, the doves seemed to be pitiable. “It can be tough for them to find a congenial shelter in the city.” I uttered in my heart, as I observed them fluttering their gray wings. It looked as if they were enjoying the serene life. Yet my brain did not cease contemplating.

Living in the era with rapid technological advancements which largely hasten our pace of life, we ineluctably forgo the joyous time being close to nature. And not until the demise of the erstwhile happiness we attained from nature comes do we realize that it is deplorable to turn ourselves into a hardened machine.

The blood-red sun was sinking and a livid cloud in the east received its rays. A twinge of woe surged through me. If we humanity kept pursuing interests by damaging the environment, what would the attendant consequence be? Would it only be driving the doves homeless?

I couldn’t help recalling the days when the city was shrouded in thick smog, and people could scarcely distinguish the things in the distance. And the rivers in the city, which were limpid before, had become turbid in recent decades. The foregoing instances were attributed to human activities. Not to mention the global warming, the ozone depletion, and the extinction of multitudinous species. Urbanization was just all of these in miniature.

The sky was tinted with black inch by inch, and the doves quieted down again. I shifted my eyes from them.

I leaned on the windowsill, looking up at the firmament, which used to be spangled with innumerable stars that were now unseen to us. Embedded aloft in the inky night sky, the pale yellow full moon cast its glow over the city, like an infinite piece of cloth mantling, yet faraway as the neon lights were, their harsh beams penetrated the textile that the moon carefully sewed without any difficulty, as if it was nonexistent. The dazzling rays pricked not only my eyes, but also my heart. “Perhaps the doves dread the blinding light, too.”

There was a time when all the doves could flit from tree to tree jovially in the dense and emerald woodlands, where they interacted with other creatures complying with the principles of nature. It was not until human beings arose that changes occurred. Trees were felled at first, and then sewage and fumes were disgorged by pipes. As the time elapsed our compunction was attenuated unawares by the profits we gained at the price of the environment we lived. We averted our gaze from what was prime, focusing on what was subordinate. The cupidity for gain and the scant heed we paid to conservation incurred the mire we confront today.

We really should pause, ruminate for a while, and inquire ourselves, what is our original orientation, and does what we endeavor to do diverge from that aim. Is our purpose to make every hue around us grey? Or to fetter ourselves in the forest of reinforced concrete? Or, to alter the earth to meet human’s multifarious demands regardless of the sustainability?

The onus is on us to maintain an agreeable environment. We need introspection, though it may seems arduous to atone for the devastation.

Fortunately, we gradually awake to the pernicious effects, and we are making a change. Eco-civilization construction has been put forward, and the departments concerned are sparing no effort to ameliorate the imbalanced ecology.

It was late spring, and every plant was flourishing. I heard the birds warbling a mellifluous night chorus, my heart mollified.

I entertain the hope that one day, we can thoroughly relish the felicity from nature. I envision an unspoiled environment. If we esteem nature, make optimal decision, and take prompt action.

I’m looking forward to the arrival of that very day.

Spring I

I heard something twittering on the balcony.

Walking on my tiptoe, I reached the window, through which I spotted a turtle dove standing on the stainless-steel-made railing, with a sprig in its beak. Barely had I observed it attentively when it hastily fled away, leaving behind a fuzzy silhouette.

I was leaning on the windowsill, looking down, when a ball of white captivated me, which I instantly recognized as peach blossoms. Bathed under the radiant sunlight, they stretched their exquisite bodies in all directions. The balmy breeze gently swayed the flowers, carrying the scent that they exuded wherever it passed. Eventually here came the spring. As I was about to return to my room, my eyes rested on a half-finished bird nest that lay on the board put on the railings.

It was unbelievable that the dove was planning to build a nest on our balcony. Yet this was the case. What’s more, I witnessed two doves erecting their lovely home together. Before long, a complete nest came out.

I could see in the mild twilight, a tiny nest lying steadily behind the huge flower pots, and an adorable dove perching on the nest. The setting sun cast its silky beams on this little cute creature through the verdant plants in the pots, resembling a warm hand patting tenderly. This tranquil scene was set off by the distant golden horizon, which formed the most enchanting landscape in the world. I could picture that under its little body, eggs were being warmed up, and new life was being brewed.

But we all know that good times do not last long, which I grasped on that drizzly evening when the dove had gone away and had not returned.

I stared at the empty nest vacantly, a sense of loss welling up in my heart. There lay the sole egg placidly, reflecting the cold light which the moon shed on the earth. Why didn’t the dove return? Maybe, I unintentionally frightened it, or, it had found a superior habitat. But, did it desert its cherished egg? On this fairly chilly rainy night, where could it go? Would it be shivering all over in the freezing wind? As the moonlight suffused the ground, I perceived that, never would I know the answer.

I leaned on the windowsill, overlooking the swaying flowers. I could hear the raindrops knocking the canopy, composing a rumpled melody agitating my thoughts. I could see them trickling down the eaves, descending, sinking into puddles, feebly splattering a spray of droplets. Also I could hear the moaning wind dashing through the alley, wildly rattling loose windows and doors. I could see it wobbling the leaves furiously, severing them from the branches and tugging them down. But, in the meantime, I could see the blossoms that the tree threw up in the air, being hit by the rain and being swung by the wind, while they kept emanating aroma that wafted all around. I could see myriad scattered petals which fell on the moist tarmac, all colors draining rapidly, yet somehow, they were peculiarly appealing with the lamplight flickering in the dewdrops.

It suddenly occurred to me that, unlike what I considered before, what was called spring, was not a picture in a particular style. It not only meant arrival and growth, but also meant departure and wilt to some extent.

So the spring is not all about a couple of turtle doves who are busy constructing a cozy neat twiggy nest where the new life will be brought, nor about the pale pink blossoms that bloom wherever you behold, adorning the corner of the bright blue sky. The essence of the spring lies in the persistence that the doves possess, even if they get so close to human beings and lose one of the only two eggs. It lies in the patience with which the dove squats in its nest unceasingly, awaiting the arrival of the baby, no matter the icy drizzle and the roaring gale. It lies in the optimism which encourages the blossoms to bloom vigorously in the frigid sprinkle. It lies in the devotion of the blossoms as they beautify the world in spite of the adversity they are confronted with.

I lingered on the balcony, hearkening wind and rain, dismay dissipating gradually. And here came the spring. I could sense that, distinctly.

The Beginning

The bell is about to ring. The new year is in sight.

Time flies as we grow and mature, leaving naivety behind. No sooner have we relived the past year in detail than we face the coming year hurriedly. Lay down the heavy burden, repack the travelling bag, take our initial dream, step forward readily and firmly.

It is said those who have received compliments should be rather careful, for other’s laud may block the consciousness of weakness, which surely leads to failure. Yet by no means shall we belittle ourselves, since nobody will have confidence in us unless we are confident. Owning a distinct understanding of oneself, cultivating the better part, remedying what have been done that turns out a mistake, are ways to adjust our mentality.

When we gaze at the vast, dark night sky, sparsely-arranged stars hang high, whispering about what they have just witnessed on this tiny, lonely, but vigorous cerulean planet, such as a large amount of teenagers burning the midnight oil, waiting for that extraordinary moment, after which they may become an adult, or may bare his or her heart to someone else, or, may just sigh with the feeling that it seems something in life, which is hard to be aware of, has vanished silently and drastically. Whatever they see, the sparkling stars keep extending their best wishes to whom they have not known and may never know. The stars, the glinting stars, the stars that split the profound night sky, for how long will we still be able to look up at you?

When we overlook the pure white snowfield, accumulated snowflakes lie serenely, mirroring the warm, aureate light that streetlamps cast, illumining the bottom of passers-by’s hearts, which originally filled with some annoying things, like working overtime without gaining anything, or getting into a conflict with someone he or she considers dearest, or, biting, frigid wind blowing right into cheek, as thousands of sharp knives pricking the skin. But at the time, the light disperses the dust, and pushes the haze in the heart aside, bringing peace and quiet, awakening hope for the future, for the year approaching. The snow, the crystal snow, the snow that decorates the empty city streets, will you still be here years later?

No matter how we get through the year just past, it does not make any sense to immerse in the memory. We shall always look forward, but don’t forget, up in the sky, down on the ground, there must be someone else, caring you, supporting you, giving you hope whenever it seems impossible.

Anyhow, it’s a brand new beginning.

Goodbye, 2018. Hello, 2019.

Light III

He can feel drizzle patting his face.

To the best of his ability, he stands up. Once more, darkness surrounds him.

He thinks about what he has just experienced, which is obviously a dreadful nightmare. Yet everything is so real, that he cannot persuade himself not to recall that dream.

In a moment, he catches sight of something in the distance, something that is gigantic enough to be seen. It is hard for him to put down the desire to approach it. He starts walking, but he senses something strange. As if he is walking through a long narrow corridor, in which there is merely extremely faint light.

When he finally reaches the thing, he is astonished to find that he is facing an infinite wall which is clearly insurmountable. Scarcely has he had time to think what is happening when he is sucked into a unbelievably strong whirlpool, losing his consciousness.

He is shocked again when he opens his eyes.

In his sight there turn seasons. He can see fresh green seedlings protruding, carefree swallows singing and dancing freely in spring, the brilliant sun creeping up gradually, tiny trees slowly growing to a huge proportion during summer, and with autumn coming the golden foliage falls, decorating the azure blue sky, before long clean white snowflakes begin to appear, which indicates that winter has reigned the ground. It is quite amazed that he is able to recognize the various colors in no time, as well as the weathers he used to feel and the planets passing over head. What he once could only heard of is just in front of him, like an ancient but exquisite picture scroll opening before his face by degrees. Wherever his vision goes, the superb landscapes appeal to him.

He is burying himself in this fabulous world when in an instant, as if a heavy gate is opened, recollections flood his brain.

He attempts to cast his mind back, and something mysterious happens.

He can see his father holding him in his arms, while his mother cradled his brother, staring at two little lives, humming a familiar song he has heard for many times. He can see he and his brother climbing up and down at home, and his brother frequently lent him a hand without which he might have fallen off the table that was still higher than him. He can see the family outing, during which his relatives didn’t get weary of guiding him, telling him what was going on around, such as fragrant flowers dancing with colorful butterflies. So joyful was he at that time that as he thinks, in his heart a knot is untied, the ice melts.

Never has he realized that so many fantastic memories have been missing since his third birthday, for which he would have lived delightedly, appreciating the love and hope on earth, summoning up the courage and confidence, to strive for an entirely different life.

But it is said there’s no sense crying over every mistake, for what has been done is unchangeable. He smiles, blandly, as he floats in the air, higher and higher.

Looking down, he sees himself, just lying, peacefully, on the snow-covered ground.


“There lies a wall, up to the heaven, down to the hell, left to infinity, right to where you cannot see.”

“This wall is called death.”

“Only when a person is confronted with this wall will he look back upon his entire life.”

Light II

He has no idea where he is.

And a strong feeling that he has never experienced before occupies his mind little by little.

The light is still there. So dim and faint is it that the dread of being encircled again by the darkness swiftly creeps up from the bottom of his heart. With all his strength though he manages to shift his feet, he can hardly make a move.

Filled with confusion, he casts a glance at the ground, but only to find blur in his sight. Apparently he is trapped in a funny dream, which is made up of what he has sustained in reality.

Weak as the light is, it still produces warmth like the sun. He knows clearly the sensation of basking. The sunlight is gentle and mild. The feeling of extreme familiarity brings him back to his childhood.

He vaguely remembers that all around him were glee and thrill when he was a infant. Often his parents took him out, holding him in the arms, bathed in the sun. Pure and innocent, he enjoyed everything he heard, smelled, touched and tasted, not being aware of that there existed something called vision, which he later thirsted for.

In his memories, his parents never love him. Oh, maybe they were, before his third birthday. It is unbelievable that a three-year-old little boy can bear so many things in mind such as hearing a baby’s weep and his parents’ mirth, as well as the realization of his disability, which have bothered him for what seems like centuries. In fact, the voices keep reverberating in his mind, and continue pushing him to the verge of collapse. He considers that day a turning point of his life.

“My third birthday.” he smiles wryly, “My last birthday.”

He has no intention, and does not willing, to grumble at his parents. What makes all the things occur is his blindness. Even he feels guilty, and believes that himself is to blame. It is him that lets his parents down, and that loses courage to live. It is his disadvantage that makes him an object of ridicule, and that surrounds him with the deepest darkness. Had he not been blind, everyone would live a better life.

Few merry moments can be found in his recollections afterwards. Or maybe.. he pretends to have forgotten them?

He does not stop searching in his memories until the light begins to fade away. His mental pain slightly alleviates as he pulls himself out of mind-wandering.

But suddenly emerging in his brain is an old saying that was told by his grandpa, which sends shivers down his spine, “Only when a person is about to depart will he look back upon his entire life.”

For the first time in his life, his heart is seized by such unimaginable fear, and it nearly stops bounding.

And there goes off the light, silently, remaining darkness.

Light I

He was born blind.

He has suffered the darkness which he is accustomed to for years, till today, when something mysterious happens.

Abruptly arising in his sight is a soft, faint beam, which seems to be a firefly in the air, a lighthouse on the sea. Confused and attracted though, he gets a sense of apprehension and decides not to move his feet, as he has never seen even a glimmer of light before.

In an instant the star-like light brightens, and it starts twinkling. His curiosity aroused, he slowly ambles towards the source, even if he cannot see it clearly. “The light is so gentle.” He thinks to himself.

He recalls the period surrounded by absolute darkness. It was not until his third birthday that he was told the earth is full of gorgeous sceneries which he wasn’t able to witness, however he hadn’t got the point and he still lived joyfully. But gradually he had no notion of what people were talking when they chatted about weathers, landscapes, and even colors. This beset him a lot, and at last, he conceded the adversity reluctantly.

He has padded for… how long? He can’t tell accurately, but he is depressed by the discovery of the fact that it is yet a long distance from where the light is emitted.

Drooped his head with a sigh, he slows his pace. “Why should I undergo all of these?” A disgruntled thought flashes in his heart, and he cannot help asking.

That people query the cause of his blindness is one of his antipathies. He has many antipathies, for instance, talking to others, but this is the very one he detests most, for always he was laughed at and was played a trick on at school, which made him consider everybody untrustworthy.

But he continues dragging himself to the light, as if he is driven by an invisible force. His mind is in a turmoil and he cannot concentrate. He is immersing in the past.

Is anyone concerned about him? He doesn’t know, yet he would like to believe there isn’t.

Occasionally he had a strong desire to leave this lightless world, the world with no hope, no laughter, and no happiness, to which he deemed himself useless. He was convinced of the meaninglessness of life, and regarded every day as suffering. He even thought up a method. Maybe… jumping off a building was a practical choice?

However, the explanation for the existence of this light remains a mystery. He doesn’t care about this. He merely wants to see the source only once, which gives out light that he has yearned for for long. His ears are brimming with the wind, as he is rushing so fast that he finds himself flying in the air.

And ultimately, he falls, asleep.

Yet light is there, still, inside his heart.

Notes on Physics

One-dimensional motion

$$
\begin{align}
v_f&=v_i+a \Delta t \\
\Delta x&=v_i \Delta t+{a \Delta t^2 \over 2} \\
\Delta x&={v_i+v_f \over 2} \Delta t \\
v_f^2&=v_i^2+2a \Delta x
\end{align}
$$

Forces and Newton’s laws of motion

$$
\begin{align}
F=ma
\end{align}
$$

Centripetal force and gravitation

$$
\begin{align}
a&={v^2 \over r}=\omega^2r \\
F&=G{m_1m_2 \over r^2}
\end{align}
$$

Work and energy

$$
\begin{align}
K&={mv^2 \over 2} \\
U_g&=F_gh=mgh \\
P&={W \over t}={Fx \over t}=Fv=mav
\end{align}
$$

Electric charge, field, and potential

$$
\begin{align}
F&=k{Q_1Q_2 \over r^2} \\
E&=k{Q \over r^2} \\
E&=2 \pi k \sigma \\
U_e&=k{Q_1Q_2 \over r} \\
V&=k{Q \over r}
\end{align}
$$

Circuits

$$
\begin{align}
R&={V \over I} \\
C&={Q \over V} \\
C&={A \over 4 \pi kd} \\
P&={U \over t}={U \over Q} \cdot {Q \over t}=VI=I^2R \\
W&=Pt=VIt=I^2Rt
\end{align}
$$

Magnetic forces, magnetic fields, and Faraday’s law

$$
\begin{align}
F&=QvB={Q \over t}(vt)B=ILB={B^2L^2v \over R} \\
B&={\mu_0I \over 2 \pi r} \\
\Phi&=BA \\
E&=N{\Delta \Phi \over \Delta t}=N{B\Delta A \over \Delta t}=NBLv \\
V_s&=V_p{N_s \over N_p}
\end{align}
$$

Momentum

$$
\begin{align}
I=mv=QLB={B^2L^2x \over R}
\end{align}
$$

Black-White Balls

题目描述

$n$ black and white balls were put into a bag. Petya doesn’t know exactly how many black balls are there among them. He knows, however, that there are $0, 1, \ldots, n$ black balls among all balls in the bag with equal probability.
Petya took $l$ balls from the bag at random, and $l_1$ of them turned out black, while $l_2$ other turned out white ($l_1+l_2=l$). Now he wants to predict how many black balls were there initially in the bag. Of course, if $l \lt n$, he can’t be sure in his prediction, but he wants to predict a segment $[a, b]$, such that the amount $k$ of black balls belongs to it with probability at least $p$.
You are given $n, l_1, l_2$ and $p$, and you must find such $a$ and $b$ that $b-a$ is minimal possible. If there are several such pairs $(a, b)$, choose the one with the smallest $a$.

题意概述

袋子里有$n$个球,每个球可能是黑色或白色。已知黑球个数在$0, 1, \ldots, n$之间等概率分布。现在从中取出$l$个球,其中有$l_1$个黑球和$l_2$个白球($l_1+l_2=l$)。要求找到一个最短的区间$[a, b]$,使得黑球个数在$[a, b]$中的概率至少为${p \over 100}$。若有多个这样的区间,输出$a$最小的。
数据范围:$1 \le n \le 50, \; 0 \le l_1 \le n, \; 0 \le l_2 \le n-l_1, \; 0 \le p \le 100$。

算法分析

令事件$A$为取出的$l$个球中有$l_1$个黑球,事件$B_i$为袋子里有$i$个黑球。根据贝叶斯定理
$$P(B_i|A)={P(B_i)P(A|B_i) \over \sum_{j=0}^n P(B_j)P(A|B_j)}$$
而我们知道
$$P(B_i)={1 \over n+1}, \; P(A|B_i)={{i \choose l_1}{n-i \choose l_2} \over {n \choose l}}$$
因此可以计算出$P(B_i|A)$,接下来只要枚举区间即可。

代码

#include <algorithm>
#include <cstdio>
#include <cstring>

static int const N = 55;
double a[N];

double get_c(int n, int m) {
  if (n < m)
    return 0;
  double ret = 1;
  for (int i = 0; i < m; ++i)
    ret *= 1. * (n - i) / (m - i);
  return ret;
}

int main() {
  int n, l1, l2, p;
  scanf("%d%d%d%d", &n, &l1, &l2, &p);
  double b = 0;
  for (int i = 0; i <= n; ++i)
    b += a[i] = 1. / (n + 1) * get_c(i, l1) * get_c(n - i, l2) / get_c(n, l1 + l2);
  for (int i = 1; i <= n + 1; ++i)
    for (int j = 0; j + i - 1 <= n; ++j) {
      double sum = 0;
      for (int k = j; k <= j + i - 1; ++k)
        sum += a[k];
      if (sum / b * 100 + 1e-12 >= p)
        return printf("%d %d\n", j, j + i - 1), 0;
    }
  return 0;
}

Fermat’s Last Theorem

题目描述

Given a positive integer $n$ and a positive prime number $p$, find $x, y$ and $z$ such that $x^n+y^n \equiv z^n \pmod p$ and $x, y$ and $z$ are nonzero modulo $p$ or report that there’s no such triple.

题意概述

给定一个整数$n$和一个质数$p$,判断方程$x^n+y^n \equiv z^n \pmod p \; (1 \le x, y, z \lt p)$是否存在整数解,若存在则给出一组解。有$T$组数据。
数据范围:$1 \le T \le 1000, \; 3 \le n \le 10^6, \; 2 \le p \le 10^6$。

算法分析

为了方便,以下同余方程模数均为$p$。
求出$p$的原根$g$,设$x=g^{k_1}, \; y=g^{k_2}, \; z=g^{k_3}$,方程变为
$$g^{k_1n}+g^{k_2n} \equiv g^{k_3n}$$
令$G=g^n$,则
$$G^{k_1}+G^{k_2} \equiv G^{k_3}$$
由于$g$是原根,可知$G \not \equiv 0$,因此
$$
\begin{align}
G^{k_1-k_2}+1 &\equiv G^{k_3-k_2} \\
G^{k_1-k_3}+G^{k_2-k_3} &\equiv 1
\end{align}
$$
根据费马小定理,$G^{p-1} \equiv 1$,所以只要从$1$到$p-1$枚举$i$,判断是否存在$j \le i$满足
$$G^i+1 \equiv G^j \lor G^j+1 \equiv G^i \lor G^i+G^j \equiv 1$$
若存在,则找到了一组解。若枚举到$i$时发现存在$j \lt i$满足$G^i \equiv G^j$,说明开始循环,直接输出无解。根据抽屉原理,枚举的次数不会太多。
此题时限较小,不能每组询问都清空数组,可以使用时间戳。

代码

#include <algorithm>
#include <cstdio>
#include <cstring>

static int const N = 1000005;
int a[N], b[N], pri[N];

int power(int a, int b, int p) {
  int ret = 1;
  for (; b; b >>= 1)
    b & 1 && (ret = 1ll * ret * a % p), a = 1ll * a * a % p;
  return ret;
}

int get_prt(int p) {
  int top = 0, k = p - 1;
  for (int i = 2; i * i <= k; ++i)
    if (!(k % i)) {
      pri[top++] = i;
      for (; !(k % i); k /= i)
        ;
    }
  if (k > 1)
    pri[top++] = k;
  for (int i = 2; i <= p - 1; ++i) {
    bool fg = 1;
    for (int j = 0; fg && j < top; ++j)
      fg &= power(i, (p - 1) / pri[j], p) > 1;
    if (fg)
      return i;
  }
  return 0;
}

int main() {
  int T;
  scanf("%d", &T);
  for (int n, p; T--;) {
    scanf("%d%d", &n, &p);
    int g = get_prt(p), gn = power(g, n, p), x = 0, y = 0, z = 0;
    for (int i = 1, G = gn; i <= p - 1; ++i, G = 1ll * G * gn % p)
      if (b[G] == T + 1)
        break;
      else {
        a[G] = i, b[G] = T + 1;
        if (b[G + 1] == T + 1) {
          x = power(g, i, p), y = 1, z = power(g, a[G + 1], p);
          break;
        }
        if (b[G - 1] == T + 1) {
          x = power(g, a[G - 1], p), y = 1, z = power(g, i, p);
          break;
        }
        if (b[1 - G + p] == T + 1) {
          x = power(g, i, p), y = power(g, a[1 - G + p], p), z = 1;
          break;
        }
      }
    x ? printf("%d %d %d\n", x, y, z) : puts("-1");
  }
  return 0;
}

Friendly Points

题目描述

Consider $n$ distinct points on a plane.
Two points from that set are said to be friends, when there exists a rectangle with sides parallel to coordinate axes that contains those two points and doesn’t contain any other point from the given set. A rectangle is said to contain a point if the point lies within the rectangle or on its border.
How many pairs of friends are there among the given points?

题意概述

给定平面上的$n$个点。定义一对点是友好点对当且仅当存在一个各边平行于坐标轴的矩形仅包含这两个点。一个点被一个矩形包含当且仅当该点在矩形内部或边界上。求有多少对友好点对。
数据范围:$1 \le n \le 10^5$。

算法分析

用CDQ分治,把平面上的问题转化为序列上的问题。将点分成上下两个部分,考虑属于不同部分的点对有多少,递归处理两个部分。
对$y$坐标分治,把两个部分中的点按$x$坐标从小到大排序,依次处理。假设处理到一个上半部分的点,当上半部分只有这个点时,下半部分可以与它构成友好点对的点的$y$坐标严格下降。因此我们可以对上半部分维护一个$y$坐标严格上升的单调栈,对下半部分维护一个$y$坐标严格下降的单调栈。在处理上半部分的某个点$p$时,用上半部分的单调栈找出$x$坐标最大的$y$坐标不大于它的点$q$,在下半部分的单调栈里二分出$x$坐标大于$q$的点有多少个,即是与$p$构成友好点对的点的个数。下半部分同理。
有一些细节:$y$坐标相同的点需放在同一部分,若某一部分中所有点的$y$坐标相同,则直接加上这一部分的答案,不递归处理;若有多个$x$坐标相同的点,上半部分只考虑$y$坐标最小的,下半部分只考虑$y$坐标最大的;两个部分中$x$坐标相同的点需同时处理。

代码

#include <algorithm>
#include <cstdio>
#include <cstring>

static int const N = 100005;
static int const MAX = 1000000001;
long long ans;
struct Point {
  int x, y;
  friend bool operator<(Point const &a, Point const &b) {
    return a.x < b.x;
  }
} p[N], s1[N], s2[N], tmp[N];

void calc(int l, int r) {
  if (l == r)
    return;
  int mid = (l + r) >> 1, L = mid - 1, R = mid + 1;
  for (; l <= L && p[L].y == p[mid].y; --L)
    ;
  for (; R <= r && p[R].y == p[mid].y; ++R)
    ;
  if (l > L && R > r) {
    std::sort(p + l, p + r + 1);
    return void(ans += r - l);
  }
  mid = l <= L ? L : R - 1;
  int p1 = l, p2 = mid + 1, p3 = l, t1 = 0, t2 = 0;
  calc(l, mid), calc(mid + 1, r);
  for (; p1 <= mid && p2 <= r;) {
    int x = std::min(p[p1].x, p[p2].x), mx = -MAX, mn = MAX;
    for (; p1 <= mid && p[p1].x == x; tmp[p3++] = p[p1++])
      mx = std::max(mx, p[p1].y);
    for (; p2 <= r && p[p2].x == x; tmp[p3++] = p[p2++])
      mn = std::min(mn, p[p2].y);
    for (; t1 && s1[t1 - 1].y < mx; --t1)
      ;
    for (; t2 && s2[t2 - 1].y > mn; --t2)
      ;
    Point r1 = t1 ? s1[t1 - 1] : (Point){-MAX, 0}, r2 = t2 ? s2[t2 - 1] : (Point){-MAX, 0};
    for (; t1 && s1[t1 - 1].y == mx; --t1)
      ;
    for (; t2 && s2[t2 - 1].y == mn; --t2)
      ;
    if (mx > -MAX)
      ans += s2 + t2 - std::upper_bound(s2, s2 + t2, r1), s1[t1++] = (Point){x, mx};
    if (mn < MAX)
      ans += s1 + t1 - std::upper_bound(s1, s1 + t1, r2), s2[t2++] = (Point){x, mn};
  }
  for (; p1 <= mid;) {
    int x = p[p1].x, mx = -MAX;
    for (; p1 <= mid && p[p1].x == x; tmp[p3++] = p[p1++])
      mx = std::max(mx, p[p1].y);
    for (; t1 && s1[t1 - 1].y < mx; --t1)
      ;
    Point r1 = t1 ? s1[t1 - 1] : (Point){-MAX, 0};
    for (; t1 && s1[t1 - 1].y == mx; --t1)
      ;
    ans += s2 + t2 - std::upper_bound(s2, s2 + t2, r1), s1[t1++] = (Point){x, mx};
  }
  for (; p2 <= r;) {
    int x = p[p2].x, mn = MAX;
    for (; p2 <= r && p[p2].x == x; tmp[p3++] = p[p2++])
      mn = std::min(mn, p[p2].y);
    for (; t2 && s2[t2 - 1].y > mn; --t2)
      ;
    Point r2 = t2 ? s2[t2 - 1] : (Point){-MAX, 0};
    for (; t2 && s2[t2 - 1].y == mn; --t2)
      ;
    ans += s1 + t1 - std::upper_bound(s1, s1 + t1, r2), s2[t2++] = (Point){x, mn};
  }
  for (int i = l; i <= r; ++i)
    p[i] = tmp[i];
}

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; ++i)
    scanf("%d%d", &p[i].x, &p[i].y);
  std::sort(p, p + n, [](Point const &a, Point const &b) { return a.y < b.y; });
  calc(0, n - 1), printf("%I64d\n", ans);
  return 0;
}