Problem:


Score : 600 points

Problem Statement

We have a set S of N points in a two-dimensional plane. The coordinates of the i-th point are (x_i, y_i). The N points have distinct x-coordinates and distinct y-coordinates.

For a non-empty subset T of S, let f(T) be the number of points contained in the smallest rectangle, whose sides are parallel to the coordinate axes, that contains all the points in T. More formally, we define f(T) as follows:

f(T) :=  (the number of integers i (1 \leq i \leq N) such that a \leq x_i \leq b and c \leq y_i \leq d, where a, b, c, and d are the minimum x-coordinate, the maximum x-coordinate, the minimum y-coordinate, and the maximum y-coordinate of the points in T)

Find the sum of f(T) over all non-empty subset T of S. Since it can be enormous, print the sum modulo 998244353.

Constraints

1 \leq N \leq 2 \times 10^5

-10^9 \leq x_i, y_i \leq 10^9

x_i \neq x_j (i \neq j)

y_i \neq y_j (i \neq j)

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
x_1 y_1
:
x_N y_N

Output

Print the sum of f(T) over all non-empty subset T of S, modulo 998244353.

Sample Input 1

3
-1 3
2 1
3 -2

Sample Output 1

13

Let the first, second, and third points be P_1, P_2, and P_3, respectively. S = \{P_1, P_2, P_3\} has seven non-empty subsets, and f has the following values for each of them:

f(\{P_1\}) = 1

f(\{P_2\}) = 1

f(\{P_3\}) = 1

f(\{P_1, P_2\}) = 2

f(\{P_2, P_3\}) = 2

f(\{P_3, P_1\}) = 3

f(\{P_1, P_2, P_3\}) = 3

The sum of these is 13.

Sample Input 2

4
1 4
2 1
3 3
4 2

Sample Output 2

34

Sample Input 3

10
19 -11
-3 -12
5 3
3 -15
8 -14
-9 -20
10 -9
0 2
-7 17
6 -6

Sample Output 3

7222

Be sure to print the sum modulo 998244353.



Sample input:
3
-1 3
2 1
3 -2


Sample output:
13

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
mod = 998244353

def sub(a, b):
    return (a % mod + mod - b % mod) % mod


def main():
    n, = list(map(int, input().split()))
    t = 1
    dd = [t]
    for _ in range(n):
        t=2*t%mod
        dd.append(t)

    xs, ys = [], []
    for _ in range(n):
        x, y = list(map(int, input().split()))
        xs.append(x)
        ys.append(y)

    ini = sorted(list(range(n)), key=lambda x:xs[x])
    for i, yi in enumerate(sorted(list(range(n)), key=lambda x:ys[x])):
        ys[yi] = i 
    nys = [ys[i] for i in ini]

    tree = [0] * (n + 1)
    r = 0
    for i, y in enumerate(nys):
        j = y+1
        while j <= n:
            tree[j] += 1
            j += j & -j

        d = 0
        j = y
        while j > 0:
            d += tree[j]
            j -= j & -j

        c = i - d
        b = (n-1) - y - c
        a = (n-1) - b - c - d
        r = (r + sub(dd[b+c] + dd[c+d] + dd[d+a] + dd[a+b],
                dd[a] + dd[b] + dd[c] + dd[d])) % mod

    print(sub((dd[n] * n) % mod, (r+n)%mod))
main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
mod = 998244353

def sub(a, b):
    return (a % mod + mod - b % mod) % mod

n, = list(map(int, input().split()))
t = 1
dd = [t]
for _ in range(n):
    t=2*t%mod
    dd.append(t)

def pow2(b):
    return dd[b]

class SegTree:
    def __init__(self, init_val, n, ide_ele, seg_func):
        self.segfunc = seg_func
        self.num = 2**(n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res

def mm(a, b, c, d, n):
    return sub(pow2(b+c) + pow2(c+d) + pow2(d+a) + pow2(a+b),
                pow2(a) + pow2(b) + pow2(c) + pow2(d))

xs, ys = [], []
for _ in range(n):
    x, y = list(map(int, input().split()))
    xs.append(x)
    ys.append(y)

ini = sorted(list(range(n)), key=lambda x:xs[x])
for i, yi in enumerate(sorted(list(range(n)), key=lambda x:ys[x])):
    ys[yi] = i 
nys = [ys[i] for i in ini]

ss1 = SegTree([0] * n, n, 0, lambda x,y:x+y)
r = 0
for i, y in enumerate(nys):
    ss1.update(y, 1)
    d = ss1.query(0, y)
    c = i - d
    b = (n-1) - y - c
    a = (n-1) - b - c - d
    r = (r + mm(a, b, c, d, n)) % mod

print(sub((pow2(n) * n) % mod, (r+n)%mod))

Submission status: Accepted

Solution code:
import sys


class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * n

    def add(self, k, x):
        while k < self.n:
            self.bit[k] += x
            k |= k + 1

    def sum(self, k):
        s = 0
        while k >= 0:
            s += self.bit[k]
            k = (k & (k + 1)) - 1
        return s


input = sys.stdin.readline
MOD = 998244353
N = int(input())
X, Y = [], []
xs, ys = {}, {}
pow2 = [1]
for i in range(N):
    pow2.append((pow2[-1] * 2) % MOD)
for i in range(N):
    x, y = map(int, input().split())
    xs[x] = 0
    ys[y] = 0
    X.append(x)
    Y.append(y)

s = 0
for i in sorted(X):
    xs[i] = s
    s += 1

s = 0
for i in sorted(Y):
    ys[i] = s
    s += 1

for i in range(N):
    X[i] = xs[X[i]]
    Y[i] = ys[Y[i]]

P = [i for i in range(N)]
P = sorted(P, key=lambda k: X[k])


bit1 = BIT(N)
bit2 = BIT(N)

for i in range(N):
    bit2.add(i, 1)

ans = 0
for i in P:
    y = Y[i]
    bit2.add(y, -1)

    A = bit1.sum(y)
    B = bit2.sum(y)
    C = bit1.sum(N - 1) - bit1.sum(y - 1)
    D = bit2.sum(N - 1) - bit2.sum(y - 1)

    ans += pow2[N - 1]
    ans %= MOD
    ans += (pow2[A] - 1) * (pow2[D] - 1) * pow2[B] * pow2[C]
    ans %= MOD
    ans += pow2[A] * pow2[D] * (pow2[B] - 1) * (pow2[C] - 1)
    ans %= MOD
    ans += MOD - ((pow2[A] - 1) * (pow2[D] - 1) * (pow2[B] - 1) * (pow2[C] - 1)) % MOD
    ans %= MOD

    bit1.add(y, 1)

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

MOD = 998244353

class BIT:
  def __init__(self, n):
    self.size = n
    self.tree = [0 for _ in range(n+1)]
    self.p = 2**(n.bit_length() - 1)
    self.dep = n.bit_length()

  def get(self, i):
    s = 0
    while i > 0:
      s += self.tree[i]
      i -= i & -i
    return s

  def add(self, i, x):
    while i <= self.size:
      self.tree[i] += x
      i += (i & -i)

  def bl(self, v):
    if v <= 0:
      return -1
    s = 0
    k = self.p
    for _ in range(self.dep):
      if s + k <= self.size and self.tree[s+k] < v:
        s += k
        v -= self.tree[s+k]
      k //= 2
    return s + 1


def compress(L):
  L2 = list(set(L))
  L2.sort()
  C = {v: k for k, v in enumerate(L2, 1)}
  return L2, C


def main():
  n = int(input())
  ans = n * pow(2, n-1, MOD) % MOD
  xy = []
  for _ in range(n):
    xy.append(tuple(map(int, input().split())))
  xy.sort()
  py = [_xy[1] for _xy in xy]
  _, Cy = compress(py)
  py = [Cy[p] for p in py]
  BIT1 = BIT(n)

  for i in range(n):
    y = py[i]  # 注目する点
    c = BIT1.get(y)  # 左下
    d = y - c - 1  # 右下
    a = i - c  # 左上
    b = n - 1 - a - c - d  # 右上
    a2 = pow(2, a, MOD)
    b2 = pow(2, b, MOD)
    c2 = pow(2, c, MOD)
    d2 = pow(2, d, MOD)
    ans += (a2-1) * b2 * c2 * (d2-1)  # 絶対に左上右下は含む
    ans += a2 * (b2-1) * (c2-1) * d2  # 絶対に右上左下は含む
    ans -= (a2-1) * (b2-1) * (c2-1) * (d2-1)  # 数えすぎ
    ans %= MOD
    BIT1.add(y, 1)

  print(ans)


if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
import itertools
import os
import sys
from collections import defaultdict

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 998244353


class BinaryIndexedTree:
    # http://hos.ac/slides/20140319_bit.pdf
    def __init__(self, size):
        """
        :param int size:
        """
        self._bit = [0] * (size + 1)
        self._size = size

    def add(self, i, w):
        """
        i 番目に w を加える
        :param int i:
        :param int w:
        :return:
        """
        x = i
        while x <= self._size:
            self._bit[x] += w
            x += x & -x

    def sum(self, i):
        """
        0 番目から i 番目までの合計
        :param int i:
        :return:
        """
        ret = 0
        x = i
        while x > 0:
            ret += self._bit[x]
            x -= x & -x
        return ret

    def __len__(self):
        return self._size


def compress(li):
    """
    大小関係を保ったまま 1 以上の数値に圧縮する。
    scipy.stats.rankdata に近い感じ
    :param list li:
    :rtype: list of int
    """
    ret = [0] * len(li)
    rank = 0
    prev = None
    for a, i in sorted([(a, i) for i, a in enumerate(li)]):
        if a != prev:
            rank += 1
        ret[i] = rank
    return ret


# 解説AC
N = int(sys.stdin.readline())
XY = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]


def test():
    ret = 0
    counts = defaultdict(int)
    for selection in itertools.product([0, 1], repeat=N):
        if not any(selection):
            continue
        xs = set([XY[i][0] for i, s in enumerate(selection) if s])
        ys = set([XY[i][1] for i, s in enumerate(selection) if s])
        xl = min(xs)
        xr = max(xs)
        yl = min(ys)
        yr = max(ys)
        r = 0
        for x, y in XY:
            r += xl <= x <= xr and yl <= y <= yr
        ret += r
        counts[r] += 1
    return ret


XY.sort()
Y = [y for _, y in XY]
Y = compress(Y)

# LL[i]: x が X[i] より小さくて、y が Y[i] より小さい数
# LG[i]: x が X[i] より小さくて、y が Y[i] より大きい数
LL = []
LG = []
GL = []
GG = []

bit = BinaryIndexedTree(size=N)
for i, y in enumerate(Y):
    ll = bit.sum(y)
    lg = i - ll
    gl = y - ll - 1
    gg = N - y - lg
    LL.append(ll)
    LG.append(lg)
    GL.append(gl)
    GG.append(gg)
    bit.add(y, 1)

pow2 = [1] * N
p = 1
for i in range(N - 1):
    p = p * 2 % MOD
    pow2[i + 1] = p

# 点 p = (X[i], Y[i]) が何回カウントされるか
ans = 0
for ll, lg, gl, gg in zip(LL, LG, GL, GG):
    # -- p を選ぶ --
    ans += pow2[N - 1]
    # -- p を選ばない --
    # ll, gg をそれぞれ1つ以上選ぶ
    a = (pow2[ll] - 1) * (pow2[gg] - 1) % MOD * pow2[N - ll - gg - 1]
    # lg, gl をそれぞれ1つ以上選ぶ
    b = (pow2[lg] - 1) * (pow2[gl] - 1) % MOD * pow2[N - lg - gl - 1]
    # ll, gg, gl, lg をそれぞれ1つ以上選ぶ
    c = (pow2[ll] - 1) * (pow2[gg] - 1) % MOD * (pow2[lg] - 1) * (pow2[gl] - 1) % MOD
    ans += a + b - c
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
import sys

class BIT:
    #1-indexed
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
        self.p = 2**(n.bit_length() - 1)
        self.dep = n.bit_length()
    
    def get(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
    
    def bl(self, v):
        if v <= 0:
            return -1
        s = 0
        k = self.p
        for _ in range(self.dep):
            if s + k <= self.size and self.tree[s+k] < v:
                s += k
                v -= self.tree[s+k]
            k //= 2
        return s + 1

def compress(L):
    L2 = list(set(L))
    L2.sort()
    C = {v : k for k, v in enumerate(L2, 1)}
    return L2, C

N = int(input())
mod = 998244353
ans = N*pow(2, N-1, mod)%mod

points = [tuple(map(int, sys.stdin.readline().split())) for _ in range(N)]
points.sort()
_, PY = map(list, zip(*points))
_, Ci = compress(PY)
PY = [Ci[p] for p in PY]
T1 = BIT(N)
T2 = BIT(N)

for i in range(1, N+1):
    T2.add(i, 1)

for i in range(N):
    y = PY[i]
    c = T1.get(y)
    d = T2.get(y)-1 - c
    a = i - c
    b = N-1 - a - c - d
    T1.add(y, 1)
    a2 = pow(2, a, mod)
    b2 = pow(2, b, mod)
    c2 = pow(2, c, mod)
    d2 = pow(2, d, mod)
    ans += (a2-1)*b2*c2*(d2-1) + a2*(b2-1)*(c2-1)*d2 - (a2-1)*(b2-1)*(c2-1)*(d2-1)
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import sys
import array

from operator import itemgetter

def main():



	input = sys.stdin.readline


	md = 998244353
	n = int(input())
	tl=n+1
	
	ft=[0]*tl

	xy = [[0]*2 for _ in range(n)]
	for i in range(n):
		xy[i] = [int(item) for item in input().split()]
	xy.sort(key=itemgetter(0))
	yxi = [y for x, y in xy]

	*YS, = set(yxi)
	YS.sort()
	yxi= list(map({e: i for i, e in enumerate(YS)}.__getitem__, yxi))

	ct=[0]*(n+1)
	ct[0]=1
	for i in range(1,n+1):
		ct[i]=ct[i-1]*2%md

	cnt=tuple(ct)

	def upd(i):
		i+=1
		while(i<=n):
			ft[i]+=1
			i+=i&-i

	def get(i):
		i+=1
		ret=0
		while(i!=0):
		    ret+=ft[i]
		    i-=i&-i
		return ret

	def calc(get,upd):
		for i, y in enumerate(yxi):
			v = get(y); upd(y)
			p1 = cnt[v]; p0 = cnt[y - v]
			q1 = cnt[i - v]; q0 = cnt[(n - y - 1) - (i - v)]
			yield (p0 + p1 + q0 + q1 - (p0 + q1) * (p1 + q0)) % md


	print((sum(calc(get,upd))+n*cnt[n] - n)%md)

main()

Submission status: Accepted

Solution code:
import sys
def solve():
    readline = sys.stdin.readline
    write = sys.stdout.write
    MOD = 998244353

    N = int(readline())
    P = [list(map(int, readline().split())) for i in range(N)]

    P.sort()

    Y = [y for x, y in P]

    def compress(X):
        *XS, = set(X)
        XS.sort()
        return list(map({e: i for i, e in enumerate(XS)}.__getitem__, X))
    Y = compress(Y)

    data = [0]*(N+1)
    def add(k, x):
        while k <= N:
            data[k] += x
            k += k & -k
    def get(k):
        s = 0
        while k:
            s += data[k]
            k -= k & -k
        return s

    pow2 = [1]*(N+1)
    r = 1
    for i in range(1, N+1):
        pow2[i] = r = r * 2 % MOD

    def gen(add, get, pow2):
        for i, y in enumerate(Y):
            v = get(y+1); add(y+1, 1)
            p1 = pow2[v]; p0 = pow2[y - v]
            q1 = pow2[i - v]; q0 = pow2[(N - y - 1) - (i - v)]
            yield (p0 + p1 + q0 + q1 - (p0 + q1) * (p1 + q0)) % MOD
    write("%d\n" % ((sum(gen(add, get, pow2)) + N*pow2[N] - N) % MOD))
solve()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
mod=998244353

class BIT():
    def __init__(self,n):
        self.size=n
        self.bit=[0]*(n+1)
    def add(self,i,x):
        while i<=self.size:
            self.bit[i]+=x
            i+=i&-i
    def sum_to_i(self,i):
        s=0
        while i>0:
            s+=self.bit[i]
            i-=i&-i
        return s

n=int(input())
XY=[]
Y=[]
for _ in range(n):
    x,y=map(int,input().split())
    XY.append((x,y))
    Y.append(y)
Y.sort()
y_dict={y:i+1 for i,y in enumerate(Y)}
XY=[(x,y_dict[y]) for x,y in XY]
XY.sort()
bit=BIT(n)
pow_2=[1]
for _ in range(n):
    pow_2.append(pow_2[-1]*2%mod)
ans=0
for i,(x,y) in enumerate(XY):
    a=bit.sum_to_i(y)
    b=i-a
    c=y-a-1
    d=(n-i-1)-c
    bit.add(y,1)
    pa,pb,pc,pd=pow_2[a],pow_2[b],pow_2[c],pow_2[d]
    tmp=pow_2[n-1]
    tmp+=(pa-1)*(pd-1)*pb*pc%mod
    tmp+=(pb-1)*(pc-1)*pa*pd%mod
    tmp-=(pa-1)*(pb-1)*(pc-1)*(pd-1)%mod
    ans+=tmp
    ans%=mod
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

XY = []
for _ in range(N):
    x, y = map(int, input().split())
    XY.append((x, y))
    
# BITの定義
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    # index 1からiの値の和を返す
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    # index iの値にxを加算する
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

#######################
# 開始
from operator import itemgetter
def solve():
    p_list = XY[:]

    # y座標の圧縮
    p_list = sorted(p_list, key=itemgetter(1))
    p_list = [ (x, y, i+1) for i, (x, y) in enumerate(p_list)]

    # xでソート
    p_list= sorted(p_list)

    # ある点が四角に含まれる場合の総数を求めるメソッド
    power = [1] * N
    for i in range(1, N):
        power[i] = power[i-1] * 2 % 998244353

    # a,bを求める
    bit = Bit(N)
    ans = 0
    for i, (x, y, r) in enumerate(p_list):
        tmp = bit.sum(r)
        a = tmp
        b = i-tmp
        c = r-tmp-1
        d = (N-r+1)-(i-tmp)-1
        bit.add(r, 1)
        _a = power[a] - 1
        _b = power[b] - 1
        _c = power[c] - 1
        _d = power[d] - 1

        ret = (_a+1) * (_d+1) * _c * _b
        ret += (_b+1) * (_c+1) * _a * _d
        ret -= _a*_b*_c*_d
        ret += power[N-1]
        ans += ret % 998244353

    print(ans % 998244353)
    
solve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

MOD = 998244353
n = int(input())
xy = []
y_index = dict() 
for i in range(n):
    x, y = [int(item) for item in input().split()]
    xy.append((x, y))
xy.sort(key=lambda x: x[1])
for i, (_, y) in enumerate(xy):
    y_index[y] = i
xy.sort()

cnt = [0] * (n+1)
def BIT_sum(i):
    ret = 0
    while i > 0:
        ret += cnt[i]
        i -= i & -i
    return ret

def BIT_add(i):
    while i <= n:
        cnt[i] += 1
        i += i & -i
    return

points_in_quad = [[0] * n for _ in range(4)]
seen = 0
for i, (x, y) in enumerate(xy):
    index = y_index[y]
    points_in_quad[2][i] = BIT_sum(index + 1)
    points_in_quad[1][i] = seen - points_in_quad[2][i] 
    BIT_add(index + 1)
    seen += 1
seen = 0
cnt = [0] * (n+1)
for i, (x, y) in enumerate(xy[::-1]):
    index = y_index[y]
    points_in_quad[3][n - 1 - i] = BIT_sum(index + 1)
    points_in_quad[0][n - 1 - i] = seen - points_in_quad[3][n - 1 - i] 
    BIT_add(index + 1)
    seen += 1

pow2 = []
a = 1
for i in range(n+1):
    pow2.append(a)
    a *= 2
    a %= MOD

ans = 0
for i in range(n):
    # target not included, n >= 2 selected
    free1 = pow2[points_in_quad[0][i]]
    free2 = pow2[points_in_quad[1][i]]
    free3 = pow2[points_in_quad[2][i]]
    free4 = pow2[points_in_quad[3][i]]
    fix24 = (free2 - 1) * (free4 - 1) % MOD
    fix13 = (free1 - 1) * (free3 - 1) % MOD
    ans -= fix24 * fix13 % MOD
    ans += ((free1 * free3) % MOD) * fix24 % MOD
    ans += ((free2 * free4) % MOD) * fix13 % MOD
    ans %= MOD
# target included, n >= 2 selected
ans += pow2[n-1] * n % MOD
print(ans % MOD)

Submission status: Accepted

Solution code:
from bisect import bisect_left
import sys
input = sys.stdin.readline

N = int(input())
xy = [[int(i) for i in input().split()] for _ in range(N)]
xy.sort()

ylist = [y for _, y in xy]
ylist.sort()
for i in range(N) :
    xy[i] = [i, bisect_left(ylist, xy[i][1])]

MOD = 998244353

def bit_sum(i) :
    s = 0
    while i > 0 :
        s += bit[i]
        i -= i & -i
    return s

def bit_add(i, x) :
    while i <= N :
        bit[i] += x
        i += i & -i

lu = [0] * N
ld = [0] * N
ru = [0] * N
rd = [0] * N

power = [1]
for _ in range(N) :
    power.append(power[-1] * 2 % MOD)

bit = [0] * (N + 1)
for i, (x, y) in enumerate(xy) :
    ld[i] = bit_sum(y+1)
    lu[i] = i - ld[i]
    bit_add(y+1, 1)

bit = [0] * (N + 1)
for i, (x, y) in enumerate(xy[::-1]) :
    rd[N-i-1] = bit_sum(y+1)
    ru[N-i-1] = i - rd[N-i-1]
    bit_add(y+1, 1)

ret = 0
for i in range(N) :
    ret += (power[lu[i]]-1)*power[ld[i]]*power[ru[i]]*(power[rd[i]]-1)
    ret += power[lu[i]]*(power[ld[i]]-1)*(power[ru[i]]-1)*power[rd[i]]
    ret -= (power[lu[i]]-1)*(power[ld[i]]-1)*(power[ru[i]]-1)*(power[rd[i]]-1)
    ret += power[lu[i]] * power[ld[i]] * power[ru[i]] * power[rd[i]]
    ret %= MOD
    
print(ret)

Submission status: Accepted

Solution code:
N = int(input())
XY = [[int(x) for x in input().split()] for i in range(N)]
mod = 998244353
XY.sort() #Xについてソート
X, Y = zip(*XY)
Y_rank = {x:i for i, x in enumerate(sorted(Y), 1)}
BIT = [0] * (N+1)

def append_BIT(x):
    while x <= N:
        BIT[x] += 1
        x += x & (-x)

def sum_BIT(x):
    ret = 0
    while x:
        ret += BIT[x]
        x &= (x-1)
    return ret

pow2 = [1]
for i in range(N):
    pow2.append(pow2[-1] * 2 % mod)

ret = 0 
for i in range(N):
    y = Y_rank[Y[i]]
    L = i
    R = N-i-1
    D = y-1
    U = N-D-1
    LD = sum_BIT(y)
    append_BIT(y)
    LU = L - LD
    RU = U - LU
    RD = D - LD
    
    ret += (pow2[N]-1 - pow2[L] - pow2[R] - pow2[U] - pow2[D] + pow2[LD] + pow2[LU] + pow2[RU] + pow2[RD])
    
ret %= mod
print(ret)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

N=int(input())
POINT=[list(map(int,input().split())) for i in range(N)]
mod=998244353

compression_dict_x={a: ind for ind, a in enumerate(sorted(set([p[0] for p in POINT])))}
POINT=[[compression_dict_x[x]+1,y] for x,y in POINT]
P_Y=sorted(POINT,key=lambda x:x[1])

# BIT(BIT-indexed tree)

LEN=len(compression_dict_x)

BIT=[0]*(LEN+1)# 1-indexedなtree

def update(v,w):# vにwを加える
    while v<=LEN:
        BIT[v]+=w
        v+=(v&(-v))# 自分を含む大きなノードへ. たとえばv=3→v=4

def getvalue(v):# [1,v]の区間の和を求める
    ANS=0
    while v!=0:
        ANS+=BIT[v]
        v-=(v&(-v))# 自分より小さい2ベキのノードへ. たとえばv=3→v=2へ
    return ANS

ANS= 4*N+(pow(2,N,mod)-1)*(N-4)%mod

for i in range(N):
    x,y=P_Y[i]
    left=getvalue(x)
    ANS=(ANS+pow(2,left,mod)+pow(2,i-left,mod)-2)%mod
    update(x,1)

P_Y.reverse()
BIT=[0]*(LEN+1)

for i in range(N):
    x,y=P_Y[i]
    left=getvalue(x)
    ANS=(ANS+pow(2,left,mod)+pow(2,i-left,mod)-2)%mod
    update(x,1)

print(ANS)

Submission status: Accepted

Solution code:

import sys
input = sys.stdin.readline
 

class BIT:
            
    def __init__(self, L):
        self.N = len(L)
        self.bit = [0]*self.N
        for i,l in enumerate(L):
            self.add(i,l)

    def add(self, a, w):
        x = a + 1
        for i in range(1000):
            self.bit[x-1] += w
            x += x & -x
            if x > self.N:
                break

    def sum(self, a):
        x = a+1
        ret = 0
        for i in range(1000):
            ret += self.bit[x-1]
            x -= x & -x
            if x <= 0:
                break        
        return ret

 
N = int(input())
point = [list(map(int,input().split())) for i in range(N)]
 
point.sort(lambda x: x[1])
for i in range(len(point)):
    point[i][1] = i
 
mod = 998244353
 
ans = ((N-4)*pow(2,N,mod)+3*N+4)%mod
 
pow2 = []
a = 1
for i in range(N+1):
    pow2.append(a)
    a *= 2
    a %= mod
 
point.sort(lambda x: x[0])
 
bit = BIT([0]*len(point))
 
 
for i,(x,y) in enumerate(point):
    if y > 0:
        ld = bit.sum(y-1)
        #ls = i//2
    else:
        ld = 0
    lu = i-ld
    rd = y - ld
    ru = N - i - 1 - rd    
    ans += pow2[lu]-1
    ans += pow2[ld]-1
    ans += pow2[ru]-1
    ans += pow2[rd]-1
    ans %= mod
    bit.add(y,1)
 
print(ans)

Submission status: Accepted

Solution code:

import sys
input = sys.stdin.readline


class SegmentTree:
    def __init__(self, L, op, default_val):
        self.op = op
        self.default_val = default_val
        self.sz = len(L)
        self.n = 1
        self.s = 1
        for i in range(1000):
            self.n *= 2
            self.s += 1
            if self.n >= self.sz:
                break
        self.node = [self.default_val]*(2*self.n-1)

        for i in range(self.sz):
            self.node[i+self.n-1] = L[i]

        for i in range(self.n-2,-1,-1):
            self.node[i] = self.op(self.node[i*2+1],self.node[i*2+2])
    
    def add(self, a, x):
        k = a+self.n-1
        self.node[k] += x
        for i in range(1000):
            k = (k-1)//2
            self.node[k] = self.op(self.node[2*k+1], self.node[2*k+2])
            if k <= 0:
                break
    
    def get(self, l, r):
        res = self.default_val
        n = self.n
        if self.sz <= r or 0 > l:
            print("ERROR: the indice are wrong.")
            return False

        for i in range(self.s):
            count = 2**i-1
            a = (r+1)//n
            b = (l-1)//n
            if a-b == 3:
                res = self.op(self.node[count+b+1],res)
                res = self.op(self.node[count+b+2],res)
                right = a*n
                left = (b+1)*n-1
                break
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                right = a*n
                left = (b+1)*n-1
                break
            n = n//2

        n1 = n//2        
        #left
        for j in range(i+1,self.s):
            count = 2**j-1 
            a = (left+1)//n1
            b = (l-1)//n1
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                left = (b+1)*n1-1                
            n1 = n1//2

        n1 = n//2        
        #right
        for j in range(i+1,self.s):
            count = 2**j-1 
            a = (r+1)//n1
            b = (right-1)//n1
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                right = a*n1                
            n1 = n1//2
        return res

N = int(input())
point = [list(map(int,input().split())) for i in range(N)]

point.sort(lambda x: x[1])
for i in range(len(point)):
    point[i][1] = i

mod = 998244353

ans = ((N-4)*pow(2,N,mod)+3*N+4)%mod

pow2 = []
a = 1
for i in range(N+1):
    pow2.append(a)
    a *= 2
    a %= mod

point.sort(lambda x: x[0])

ST = SegmentTree([0]*len(point), lambda a,b:a+b, 0)


for i,(x,y) in enumerate(point):
    if point[i][1] > 0:
        ld = ST.get(0,y-1)
        #ls = i//2
    else:
        ld = 0
    lu = i-ld
    rd = y - ld
    ru = N - i - 1 - rd    
    ans += pow2[lu]-1
    ans += pow2[ld]-1
    ans += pow2[ru]-1
    ans += pow2[rd]-1
    ans %= mod
    ST.add(point[i][1],1)

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import bisect

MOD = 998244353  # type: int

class BitIndexedTree(object):
    def __init__(self, N):
        self.V = [0] * N
        self.N = N
    
    def __getitem__(self, key):
        return self.sum(key, key+1)
    
    def __setitem__(self, key, value):
        diff = value - self[key]
        self.add(diff, key)

    def add(self, w, a):
        if w == 0:
            return
        x = a
        while x <= self.N:
            self.V[x-1] += w
            x += x & -x
    
    def sum(self, start=0, end=0):
        if end <= start:
            return 0
        if start > 0:
            return self.sum(0, end) - self.sum(0, start)
        x = end
        ret = 0
        while x > 0:
            ret += self.V[x-1]
            x -= x & -x
        return ret


def solve(N: int, P: "List[tuple]"):
    res = 0
    power = [1] * N
    for i in range(1, N):
        power[i] = power[i-1] * 2 % MOD

    P.sort(key=lambda x: x[1])
    for i, p in enumerate(P):
        p[1] = i
    
    P.sort()
    for i, p in enumerate(P):
        p[0] = i
    left = BitIndexedTree(N)
    right = BitIndexedTree(N)

    ll = [0] * N
    lg = [0] * N
    gl = [0] * N
    gg = [0] * N

    for i, p in enumerate(P):
        ll[i] = left.sum(0, p[1])
        lg[i] = i-ll[i]
        left.add(1, p[1]+1)

    for i, p in enumerate(P[::-1]):
        gl[-1-i] = right.sum(0, p[1])
        gg[-1-i] = i-gl[-1-i]
        right.add(1, p[1]+1)

    for a1, a2, a3, a4 in zip(gg, lg, ll, gl):
        b1 = power[a1]
        b2 = power[a2]
        b3 = power[a3]
        b4 = power[a4]

        res += (b1 - 1) * (b3 - 1) * b2 * b4
        res += (b2 - 1) * (b4 - 1) * b1 * b3

        res -= (b1 - 1) * (b2 - 1) * (b3 - 1) * (b4 - 1)

        res += power[N-1]

        res %= MOD
    print(res)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    P = [()] * (N)  # type: "List[tuple]" 
    for i in range(N):
        x = int(next(tokens))
        y = int(next(tokens))
        P[i] = [x, y]
    solve(N, P)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import bisect

MOD = 998244353  # type: int

class BitIndexedTree(object):
    def __init__(self, N):
        self.V = [0] * N
        self.N = N
    
    def __getitem__(self, key):
        return self.sum(key, key+1)
    
    def __setitem__(self, key, value):
        diff = value - self[key]
        self.add(diff, key)

    def add(self, w, a):
        if w == 0:
            return
        x = a
        while x <= self.N:
            self.V[x-1] += w
            x += x & -x
    
    def sum(self, start=0, end=0):
        if end <= start:
            return 0
        if start > 0:
            return self.sum(0, end) - self.sum(0, start)
        x = end
        ret = 0
        while x > 0:
            ret += self.V[x-1]
            x -= x & -x
        return ret


def solve(N: int, P: "List[tuple]"):
    res = 0
    power = [1] * N
    for i in range(1, N):
        power[i] = power[i-1] * 2 % MOD

    P.sort(key=lambda x: x[1])
    for i, p in enumerate(P):
        p[1] = i
    
    P.sort()
    for i, p in enumerate(P):
        p[0] = i
    left = BitIndexedTree(N)
    right = BitIndexedTree(N)

    ll = [0] * N
    lg = [0] * N
    gl = [0] * N
    gg = [0] * N

    for i, p in enumerate(P):
        ll[i] = left.sum(0, p[1])
        lg[i] = i-ll[i]
        left.add(1, p[1]+1)

    for i, p in enumerate(P[::-1]):
        gl[-1-i] = right.sum(0, p[1])
        gg[-1-i] = i-gl[-1-i]
        right.add(1, p[1]+1)

    for a1, a2, a3, a4 in zip(gg, lg, ll, gl):
        b1 = power[a1]
        b2 = power[a2]
        b3 = power[a3]
        b4 = power[a4]

        res += (b1 - 1) * (b3 - 1) * b2 * b4
        res += (b2 - 1) * (b4 - 1) * b1 * b3

        res -= (b1 - 1) * (b2 - 1) * (b3 - 1) * (b4 - 1)

        res += b1 * b2 * b3 * b4

        res %= MOD
    print(res)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    P = [()] * (N)  # type: "List[tuple]" 
    for i in range(N):
        x = int(next(tokens))
        y = int(next(tokens))
        P[i] = [x, y]
    solve(N, P)

if __name__ == '__main__':
    main()