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 .

Solution (Python):
import sys
S=sys.stdin.readlines()
def Binit(B,siz):
  while len(B)<siz+1:
    B.append(0)
  while len(B)>siz+1:
    del B[-1]
  for i in range(siz+1):
    B[i]=0
  B.append(siz)

def Badd(B,a,x):
  z=a
  while z<=B[-1]:
    B[z]+=x
    z+=(z&(-z))

def Bsum(B,a):
  r=0
  z=a
  while z>0:
    r+=B[z]
    z-=(z&(-z))
  return r

def Bssum(B,a,b):
  return Bsum(B,max(a,b))-Bsum(B,min(a,b)-1)

N=int(S[0])
X=[list(map(int,S[i+1].split())) for i in range(N)]
X.sort()
for i in range(N):
  X[i][0]=i
D=dict()
Y=sorted([X[i][1] for i in range(N)])
for i in range(N):
  D[Y[i]]=i
for i in range(N):
  X[i][1]=D[X[i][1]]
B1,B2=[],[]
Binit(B1,N+1)
Binit(B2,N+1)
for i in range(N):
  Badd(B2,i+1,1)
mod=998244353
P=N*pow(2,N-1,mod)%mod
Z=[[1,1,1,1],[1,1,1,0],[1,1,0,1],[1,0,1,1],[1,0,0,1],[0,1,1,1],[0,1,1,0]]
A=0
for i in range(N):
  Badd(B2,X[i][1]+1,-1)
  V=[Bsum(B1,X[i][1]+1),Bsum(B2,X[i][1]+1)]
  W=[pow(2,V[0],mod)-1,pow(2,i-V[0],mod)-1,pow(2,V[1],mod)-1,pow(2,N-i-1-V[1],mod)-1]
  for j in range(7):
    A=1
    if Z[j][0]:
      A=A*W[0]%mod
    if Z[j][1]:
      A=A*W[1]%mod
    if Z[j][2]:
      A=A*W[2]%mod
    if Z[j][3]:
      A=A*W[3]%mod
    P=(P+A)%mod
  Badd(B1,X[i][1]+1,1)
print(P)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")



def init(bit, values):
    for i,v in enumerate(values):
        add(bit,i+1,v)

def query(bit,i):
    res = 0
    while i > 0:
        res += bit[i]
        i -= i&(-i)
    return res


def add(bit,i,x):
    if i==0:
        raise RuntimeError
    while i <= len(bit)-1:
        bit[i] += x
        i += i&(-i)
    return

n = int(input())
xy = [tuple(map(int, input().split())) for _ in range(n)]
from bisect import bisect_left
def press(l):
    
    xs = sorted(set(l))
    inds = [None] * len(l)
    for i,item in enumerate(l):
        inds[i] = bisect_left(xs, item)
    return xs, inds
_, indx = press([item[0] for item in xy])
_, indy = press([item[1] for item in xy])
xy = []
for i in range(n):
    xy.append(indy[i]+indx[i]*n)
xy.sort()
M = 998244353

pows = [0]*(n+1)
v = 1
for i in range(n+1):
    pows[i] = v-1
    v *= 2
    v %= M
ans = (pows[n]*n) % M
bit = [0]*(n+1)
for i in range(n):
    x,y = divmod(xy[i],n)
    ans -= pows[i] + pows[n-i-1]
    ans += pows[query(bit, y+1)] + pows[i - query(bit, y+1)]
    add(bit, y+1, 1)
    ans %= M
from operator import itemgetter
xy.sort(key=lambda item: item%n)
bit = [0]*(n+1)
for i in range(n):
    x,y = divmod(xy[i],n)
    ans -= pows[i] + pows[n-i-1]
    ans += pows[i - query(bit, x+1)]
    add(bit, x+1, 1)
    ans %= M
bit = [0]*(n+1)
for i in range(n-1, -1, -1):
    x,y = divmod(xy[i], n)
    ans += pows[(n-1-i) - query(bit, x+1)]
    add(bit, x+1, 1)
    ans %= M
print(ans%M)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")



def init(bit, values):
    for i,v in enumerate(values):
        add(bit,i+1,v)

def query(bit,i):
    res = 0
    while i > 0:
        res += bit[i]
        i -= i&(-i)
    return res


def add(bit,i,x):
    if i==0:
        raise RuntimeError
    while i <= len(bit)-1:
        bit[i] += x
        i += i&(-i)
    return

n = int(input())
xy = [tuple(map(int, input().split())) for _ in range(n)]
from bisect import bisect_left
def press(l):
    
    xs = sorted(set(l))
    inds = [None] * len(l)
    for i,item in enumerate(l):
        inds[i] = bisect_left(xs, item)
    return xs, inds
_, indx = press([item[0] for item in xy])
_, indy = press([item[1] for item in xy])
xy = list(zip(indx, indy))
xy.sort()
M = 998244353

pows = [0]*(n+1)
v = 1
for i in range(n+1):
    pows[i] = v-1
    v *= 2
    v %= M
ans = (pows[n]*n) % M
bit = [0]*(n+1)
for i,(x,y) in enumerate(xy):
    ans -= pows[i] + pows[n-i-1]
    ans += pows[query(bit, y+1)] + pows[i - query(bit, y+1)]
    add(bit, y+1, 1)
    ans %= M
from operator import itemgetter
xy.sort(key=itemgetter(1))
bit = [0]*(n+1)
for i,(x,y) in enumerate(xy):
    ans -= pows[i] + pows[n-i-1]
    ans += pows[i - query(bit, x+1)]
    add(bit, x+1, 1)
    ans %= M
bit = [0]*(n+1)
for i in range(n-1, -1, -1):
    x,y = xy[i]
    ans += pows[(n-1-i) - query(bit, x+1)]
    add(bit, x+1, 1)
    ans %= M
print(ans%M)

Solution (Python):
import sys
import io, os

input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

mod = 998244353

def main():
    n = int(input())
    XY = []
    X = set()
    Y = set()
    for i in range(n):
        x,y = map(int, input().split())
        XY.append((x, y))
        X.add(x)
        Y.add(y)

    X = list(X)
    Y = list(Y)
    X.sort()
    Y.sort()
    dx = {}
    for i, x in enumerate(X):
        dx[x] = i
    dy = {}
    for i, y in enumerate(Y):
        dy[y] = i

    XY.sort()
    XY = [(dx[x], dy[y]) for x, y in XY]

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

        def init(self, init_val):
            for i, v in enumerate(init_val):
                self.add(i, v)

        def add(self, i, x):
            
            i += 1 
            while i <= self.n:
                self.bit[i] += x
                i += (i & -i)

        def sum(self, i, j):
            
            
            return self._sum(j) - self._sum(i)

        def _sum(self, i):
            
            
            res = 0
            while i > 0:
                res += self.bit[i]
                i -= i & (-i)
            return res

        def lower_bound(self, x):
            s = 0
            pos = 0
            depth = self.n.bit_length()
            v = 1 << depth
            for i in range(depth, -1, -1):
                k = pos + v
                if k <= self.n and s + self.bit[k] < x:
                        s += self.bit[k]
                        pos += v
                v >>= 1
            return pos

    UL = [0]*n
    UR = [0]*n
    LL = [0]*n
    LR = [0]*n

    bit = BIT(2*10**5+5)
    for i in range(n):
        x, y = XY[i]
        LL[i] = bit.sum(0, y+1)
        UL[i] = i-LL[i]
        bit.add(y, 1)

    bit = BIT(2*10**5+5)
    for i in reversed(range(n)):
        x, y = XY[i]
        LR[i] = bit.sum(0, y+1)
        UR[i] = (n-1-i)-LR[i]
        bit.add(y, 1)

    
    
    
    

    ans = 0
    for i in range(n):
        ans += (pow(2, UL[i], mod)-1)*(pow(2, LR[i], mod)-1)*pow(2, UR[i], mod)*pow(2, LL[i], mod)
        ans += pow(2, UL[i], mod)*pow(2, LR[i], mod)*(pow(2, UR[i], mod)-1)*(pow(2, LL[i], mod)-1)
        ans -= (pow(2, UL[i], mod)-1)*(pow(2, LR[i], mod)-1)*(pow(2, UR[i], mod)-1)*(pow(2, LL[i], mod)-1)
        ans += pow(2, UL[i], mod)*pow(2, LR[i], mod)*pow(2, UR[i], mod)*pow(2, LL[i], mod)
        ans %= mod
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
import math

input = sys.stdin.readline

class BIT:
    def __init__(self, len_A):
        self.N = len_A + 10
        self.bit = [0]*(len_A+10)

    def query(self, i):
        res = 0
        idx = i+1
        while idx:
            res += self.bit[idx]
            idx -= idx & (-idx)
        return res

    def update(self, i, x):
        idx = i+1
        while idx < self.N:
            self.bit[idx] += x
            idx += idx & (-idx)

    def lower_left(self, w):
        if (w < 0):
            return -1
        x = 0
        k = 1 << (self.N.bit_length()-1)
        while k > 0:
            if x+k < self.N and self.bit[x+k] < w:
                w -= self.bit[x+k]
                x += k
            k //= 2
        return x


N = int(input())
xy = sorted([list(map(int, input().split())) for _ in range(N)], key=lambda x: x[1])
P = 998244353


for i in range(N):
    xy[i][1] = i
xy = sorted(xy)
for i in range(N):
    xy[i][0] = i


ld, lu, rd, ru = [-1] * N, [-1] * N, [-1] * N, [-1] * N

bit = BIT(N)

for i in range(N):
    ld[i] = bit.query(xy[i][1])
    lu[i] = bit.query(N) - ld[i]
    bit.update(xy[i][1], 1)

bit = BIT(N)

for i in range(N-1, -1, -1):
    rd[i] = bit.query(xy[i][1])
    ru[i] = bit.query(N) - rd[i]
    bit.update(xy[i][1], 1)

ans = 0  
for i in range(N):
    ans = (ans + pow(2, N, P) - 1) % P
    ans = (ans - (pow(2, rd[i] + ru[i], P)-1 )) % P
    ans = (ans - (pow(2, ld[i] + lu[i], P) - 1)) % P
    ans = (ans - (pow(2, rd[i] + ld[i], P) - 1)) % P
    ans = (ans - (pow(2, ru[i] + lu[i], P) - 1)) % P
    ans = (ans + (pow(2, ru[i], P) - 1)) % P
    ans = (ans + (pow(2, rd[i], P) - 1)) % P
    ans = (ans + (pow(2, lu[i], P) - 1)) % P
    ans = (ans + (pow(2, ld[i], P) - 1)) % P
print(ans)

Solution (Python):




N = int(input())
xy = [tuple(map(int,input().split())) for _ in range(N)]

mod = 998244353

class BIT:
    '''https://tjkendev.github.io/procon-library/python/range_query/bit.html'''
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s
    def add(self, i, x):
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    def query(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)




xy2 = []
Y = []
for i in range(N):
  x,y = xy[i]
  Y.append(y)
  x += 10**9
  y += 10**9
  xy2.append(x<<80 | y << 40 | i)

Y = sorted(Y)
y_compress = {Y[i]:i+1 for i in range(N)}
  
xy2 = sorted(xy2)
mask = (1<<40)-1
bit=BIT(N)


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

ans = 0
for x in xy2:
  i = x & mask
  x >>= 40
  y = x & mask
  y -= 10**9
  x >>= 40
  x -= 10**9
  
  y = y_compress[y]
  bit.add(y,1)
  '''
  今現在みている点より左上と左下にある点の個数（今の点は含まない。以下同じ）。
  BITを使って求める。
  '''
  n1 = bit.query(y-1,N)-1
  n2 = bit.query(0,y)-1 
  '''
  右上と右下。座標圧縮の結果を利用。(N-y(座標圧縮済))はある点より上にある点の総数。
  そこからn1（走査済みの点の個数)を引くことで、まだ走査していない点の個数を求めることができる。
  '''
  n3 = N-y-n1 
  n4 = y-n2-1
  
  prod14 = (pow2[n1]-1)*(pow2[n4]-1)*pow2[n2+n3] %mod
  prod23 = (pow2[n2]-1)*(pow2[n3]-1)*pow2[n1+n4] %mod
  prod1234 = (pow2[n1]-1)*(pow2[n4]-1)*(pow2[n2]-1)*(pow2[n3]-1) %mod
  ans += pow2[N-1]+prod14+prod23-prod1234
  ans %= mod
  
print(ans)

Solution (Python):




N = int(input())
xy = [tuple(map(int,input().split())) for _ in range(N)]

mod = 998244353

class BIT:
    '''https://tjkendev.github.io/procon-library/python/range_query/bit.html'''
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s
    def add(self, i, x):
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    def query(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)


xy2 = []
for i in range(N):
  x,y = xy[i]
  x += 10**9
  y += 10**9
  xy2.append(y<<80 | x << 40 | i)



xy2 = sorted(xy2)
mask = (1<<40)-1
y_order=[0]*N
y_compress={}
for j,y in enumerate(xy2):
  i = y & mask
  y >>= 40
  x = y & mask
  x -= 10**9
  y >>= 40
  y -= 10**9
  y_order[i] = j
  y_compress[y] = j+1

xy2 = []
for i in range(N):
  x,y = xy[i]
  x += 10**9
  y += 10**9
  xy2.append(x<<80 | y << 40 | i)
  
xy2 = sorted(xy2)
mask = (1<<40)-1
bit=BIT(N)
ans = 0
memo=[0]*N


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

for x in xy2:
  i = x & mask
  x >>= 40
  y = x & mask
  y -= 10**9
  x >>= 40
  x -= 10**9
  
  y = y_compress[y]
  bit.add(y,1)
  '''
  今現在みている点より左上と左下にある点の個数（今の点は含まない。以下同じ）。
  BITを使って求める。
  '''
  n1 = bit.query(y-1,N)-1
  n2 = bit.query(0,y)-1 
  '''
  右上と右下。座標圧縮の結果を利用。(N-y(座標圧縮済))はある点より上にある点の総数。
  そこからn1（走査済みの点の個数)を引くことで、まだ走査していない点の個数を求めることができる。
  '''
  n3 = N-y-n1 
  n4 = y-n2-1
  
  prod14 = (pow2[n1]-1)*(pow2[n4]-1)*pow2[n2+n3] %mod
  prod23 = (pow2[n2]-1)*(pow2[n3]-1)*pow2[n1+n4] %mod
  prod1234 = (pow2[n1]-1)*(pow2[n4]-1)*(pow2[n2]-1)*(pow2[n3]-1) %mod
  ans += pow2[N-1]+prod14+prod23-prod1234
  ans %= mod
  
print(ans)

Solution (Python):




N = int(input())
xy = [tuple(map(int,input().split())) for _ in range(N)]

mod = 998244353

class BIT:
    '''https://tjkendev.github.io/procon-library/python/range_query/bit.html'''
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s
    def add(self, i, x):
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    def query(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)


xy2 = []
for i in range(N):
  x,y = xy[i]
  x += 10**9
  y += 10**9
  xy2.append(y<<80 | x << 40 | i)



xy2 = sorted(xy2)
mask = (1<<40)-1
y_order=[0]*N
y_compress={}
for j,y in enumerate(xy2):
  i = y & mask
  y >>= 40
  x = y & mask
  x -= 10**9
  y >>= 40
  y -= 10**9
  y_order[i] = j
  y_compress[y] = j+1

xy2 = []
for i in range(N):
  x,y = xy[i]
  x += 10**9
  y += 10**9
  xy2.append(x<<80 | y << 40 | i)
  
xy2 = sorted(xy2)
mask = (1<<40)-1
bit=BIT(N)
ans = 0
memo=[0]*N


def pow2(x):
  if memo[x-1]:return memo[x-1]
  out = pow(2,x,mod)
  memo[x-1] = out
  return out

for x in xy2:
  i = x & mask
  x >>= 40
  y = x & mask
  y -= 10**9
  x >>= 40
  x -= 10**9
  
  y = y_compress[y]
  bit.add(y,1)
  '''
  今現在みている点より左上と左下にある点の個数（今の点は含まない。以下同じ）。
  BITを使って求める。
  '''
  n1 = bit.query(y-1,N)-1
  n2 = bit.query(0,y)-1 
  '''
  右上と右下。座標圧縮の結果を利用。(N-y(座標圧縮済))はある点より上にある点の総数。
  そこからn1（走査済みの点の個数)を引くことで、まだ走査していない点の個数を求めることができる。
  '''
  n3 = N-y-n1 
  n4 = y-n2-1
  
  prod14 = (pow2(n1)-1)*(pow2(n4)-1)*pow2(n2+n3) %mod
  prod23 = (pow2(n2)-1)*(pow2(n3)-1)*pow2(n1+n4) %mod
  prod1234 = (pow2(n1)-1)*(pow2(n4)-1)*(pow2(n2)-1)*(pow2(n3)-1) %mod
  ans += pow2(N-1)+prod14+prod23-prod1234
  ans %= mod
  
print(ans)

Solution (Python):




N = int(input())
xy = [tuple(map(int,input().split())) for _ in range(N)]

mod = 998244353

class BIT:
    '''https://tjkendev.github.io/procon-library/python/range_query/bit.html'''
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s
    def add(self, i, x):
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    def query(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)


xy2 = []
for i in range(N):
  x,y = xy[i]
  x += 10**9
  y += 10**9
  xy2.append(y<<80 | x << 40 | i)



xy2 = sorted(xy2)
mask = (1<<40)-1
y_order=[0]*N
y_compress={}
for j,y in enumerate(xy2):
  i = y & mask
  y >>= 40
  x = y & mask
  x -= 10**9
  y >>= 40
  y -= 10**9
  y_order[i] = j
  y_compress[y] = j+1

xy2 = []
for i in range(N):
  x,y = xy[i]
  x += 10**9
  y += 10**9
  xy2.append(x<<80 | y << 40 | i)
  
xy2 = sorted(xy2)
mask = (1<<40)-1
bit=BIT(N)
ans = 0
for x in xy2:
  i = x & mask
  x >>= 40
  y = x & mask
  y -= 10**9
  x >>= 40
  x -= 10**9
  
  y = y_compress[y]
  bit.add(y,1)
  '''
  今現在みている点より左上と左下にある点の個数（今の点は含まない。以下同じ）。
  BITを使って求める。
  '''
  n1 = bit.query(y-1,N)-1
  n2 = bit.query(0,y)-1 
  '''
  右上と右下。座標圧縮の結果を利用。(N-y(座標圧縮済))はある点より上にある点の総数。
  そこからn1（走査済みの点の個数)を引くことで、まだ走査していない点の個数を求めることができる。
  '''
  n3 = N-y-n1 
  n4 = y-n2-1
  prod14 = (pow(2,n1,mod)-1)*(pow(2,n4,mod)-1)*pow(2,n2+n3,mod) %mod
  prod23 = (pow(2,n2,mod)-1)*(pow(2,n3,mod)-1)*pow(2,n1+n4,mod) %mod
  prod1234 = (pow(2,n1,mod)-1)*(pow(2,n4,mod)-1)*(pow(2,n2,mod)-1)*(pow(2,n3,mod)-1) %mod
  ans += pow(2,N-1,mod)+prod14+prod23-prod1234
  ans %= mod
  
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))


"""
f(T)=iなるTの通り数を数えるか，
f(T)=1がN通り，f(T)=Nはいっぱい．上下左右それぞれのmaxを選び，中のものがm個であるとき2^m通り
x座標，y座標が全て相異なるのが嬉しいかも，でも，これめんどくさすぎる

ある1つの点が与える寄与を考える，

その頂点をTに含む場合＝＞必ず+1 * 2^(N-1)通り

その頂点をTに含まない場合
（右上から1つ以上，左下から1つ以上），（右下から1つ以上，左上から1つ以上）の組なら加算
これらの組みは重複しそうなので，うまく被らないように選ぶ必要あり
（右上，左下，左上0，右下0），（右上，左下，左上，右下0），（右上，左下，左上0，右下）みたいに分けて考える．

でも，各頂点ごとに４つの方向それぞれの頂点数を持つのがまず難しい．
頂点を左から順に走査．左にある頂点の個数を上下別に見ていく．
(左上，左下)を考える．
一番左なら(0,0)，次のものは(0,1) or (1,0)みたいな．見た頂点のy座標(座圧したもの)をsegTreeで管理すれば，上下の個数がそれぞれわかる．

終わったら右からもやれば4方向それぞれの個数が分かりそう．
"""
def main():
    mod=998244353
    class SegTree:
        def __init__(self,N,ide,segfunc=min):
            self.ide_ele = ide
            """
            ex)
             最小値のセグ木 → +inf
              和のセグ木 → 0
              積のセグ木 → 1
              gcdのセグ木 → 0
            """
            
            self.segfunc=segfunc
            
            
            self.num =2**(N-1).bit_length()
            self.seg=[self.ide_ele]*2*self.num

        
        def setL(self,init_val):
            
            for i in range(self.num):
                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:
                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
    N=I()
    Y=[0]*N
    from collections import defaultdict
    ddy = defaultdict(int)
    
    L=[[0,0,0]for _ in range(N)]
    for i in range(N):
        x,y=MI()
        Y[i]=y
        L[i]=[x,y,i]
        
    
    Y.sort()
    for i in range(N):
        ddy[Y[i]]=i
    
    
    POW=[1]
    for i in range(N+5):
        p=(POW[-1]*2)%mod
        POW.append(p)
    
    cnt=[[0,0,0,0]for _ in range(N)]
    
    
    L.sort()
    
    seg=SegTree(N,0,lambda a,b: a+b)
    for j in range(N):
        i=L[j][2]
        y=L[j][1]
        yy=ddy[y]
        temp=seg.query(yy,N)
        cnt[i][0]=temp
        cnt[i][1]=j-temp
        
        seg.update(yy,1)
        
    
    seg=SegTree(N,0,lambda a,b: a+b)
    for j in range(N):
        i=L[-1-j][2]
        y=L[-1-j][1]
        yy=ddy[y]
        temp=seg.query(yy,N)
        cnt[i][2]=temp
        cnt[i][3]=j-temp
        seg.update(yy,1)
        
    def calc(cnt_item):
        
        lu,ld,ru,rd=cnt_item
        
        temp=POW[N-1]
        
        
        
        
        temp+=((POW[lu]-1) * (POW[rd]-1))%mod
        
        temp+=((POW[ld]-1) * (POW[ru]-1))%mod
        
        
        temp+=((POW[lu]-1) * (POW[ld]-1) *  (POW[ru]-1))%mod
        
        temp+=((POW[lu]-1) * (POW[ld]-1) * (POW[rd]-1))%mod
        
        temp+=((POW[lu]-1) *  (POW[ru]-1) * (POW[rd]-1))%mod
        
        temp+=((POW[ld]-1) *  (POW[ru]-1) * (POW[rd]-1))%mod
        
        
        temp+=((POW[lu]-1) * (POW[ld]-1) *  (POW[ru]-1) * (POW[rd]-1))%mod
        
        temp%=mod
        
        
        return temp
    
    ans=0
    for i in range(N):
        
        ans=(ans+calc(cnt[i]))%mod
        
    print(ans)




main()

Solution (Python):
import sys
readline = sys.stdin.readline

class BIT:
    
    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)}
    return L2, C


MOD = 998244353
N = int(readline())
XY = [list(map(int, readline().split())) for _ in range(N)]
XY.sort()

Z = [-10**10]
for x, y in XY:
    Z.append(y)

_, CC = compress(Z)
XY = [(x, CC[y]) for x, y in XY] 

SS, SB, BS, BB = [None]*N, [None]*N, [None]*N, [None]*N

T = BIT(N)
for i in range(N):
    k = i
    y = XY[i][1]
    l = T.get(y)
    SS[i] = l
    SB[i] = k-l
    T.add(y, 1)
T = BIT(N)
for i in range(N-1, -1, -1):
    k = N-1-i
    y = XY[i][1]
    l = T.get(y)
    BS[i] = l
    BB[i] = k-l
    T.add(y, 1)

P2 = [1]*1341398
for i in range(1, len(P2)):
    P2[i] = P2[i-1]*2%MOD

ans = 0
for i in range(N):
    ss = SS[i]
    sb = SB[i]
    bs = BS[i]
    bb = BB[i]
    ans = (ans + P2[N-1])%MOD
    ans = (ans + P2[N-1-ss-bb]*(P2[ss]-1)*(P2[bb]-1))%MOD
    ans = (ans + P2[N-1-sb-bs]*(P2[sb]-1)*(P2[bs]-1))%MOD
    ans = (ans - (P2[sb]-1)*(P2[bs]-1)*(P2[ss]-1)*(P2[bb]-1))%MOD
    
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
mod = 998244353
n = int(input())
XY = sorted(tuple(map(int, input().split())) for _ in range(n))
X, Y = zip(*XY)
L = {y:i+1 for i, y in enumerate(sorted(Y))}
Y = tuple(L[y] for y in Y)
BIT = [0]*(n+1)
def add(i):
  while i<=n:
    BIT[i] += 1
    i += i&-i
def acc(i):
  res = 0
  while i:
    res += BIT[i]
    i -= i&-i
  return res
A = [0]*n
B = [0]*n
C = [0]*n
D = [0]*n
for i, y in enumerate(Y):
  A[i] = acc(y)
  B[i] = i - A[i]
  add(y)
BIT = [0]*(n+1)
for i in range(n-1, -1, -1):
  y = Y[i]
  C[i] = acc(y)
  D[i] = n-1-i - C[i]
  add(y)
T = [1]*n
for i in range(n-1):
  T[i+1] = T[i]*2%mod
ans = T[n-1] * n % mod
for a, b, c, d in zip(A, B, C, D):
  a = T[a]
  b = T[b]
  c = T[c]
  d = T[d]
  temp = (a-1)*b*c*(d-1) + a*(b-1)*(c-1)*d - (a-1)*(b-1)*(c-1)*(d-1)
  ans += temp
  ans %= mod
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
mod = 998244353
n = int(input())
XY = sorted(tuple(map(int, input().split())) for _ in range(n))
X, Y = zip(*XY)
L = {y:i+1 for i, y in enumerate(sorted(Y))}
Y = tuple(L[y] for y in Y)
BIT = [0]*(n+1)
def add(i):
  while i<=n:
    BIT[i] += 1
    i += i&-i
def acc(i):
  res = 0
  while i:
    res += BIT[i]
    i -= i&-i
  return res
A = [0]*n
B = [0]*n
C = [0]*n
D = [0]*n
for i, y in enumerate(Y):
  A[i] = acc(y)
  B[i] = i - A[i]
  add(y)
BIT = [0]*(n+1)
for i in range(n-1, -1, -1):
  y = Y[i]
  C[i] = acc(y)
  D[i] = n-1-i - C[i]
  add(y)
ans = pow(2, n-1, mod) * n % mod
for a, b, c, d in zip(A, B, C, D):
  a = pow(2, a, mod)
  b = pow(2, b, mod)
  c = pow(2, c, mod)
  d = pow(2, d, mod)
  temp = (a-1)*b*c*(d-1) + a*(b-1)*(c-1)*d - (a-1)*(b-1)*(c-1)*(d-1)
  ans += temp
  ans %= mod
print(ans)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

class Seg_sum():
    def __init__(self,x):
        
        self.ide_ele_min = 0
        self.func = lambda a,b : a+b

        self.n = len(x)

        
        self.num_max =2**(self.n-1).bit_length()
        self.x = [self.ide_ele_min]*2*self.num_max

        for i,num in enumerate(x, self.num_max):
            self.x[i] = num
        for i in range(self.num_max-1,0,-1):
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def update(self,i,x):
        i += self.num_max
        self.x[i] = x
        while(i>0):
            i = i//2
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def query(self,i,j):
        res = self.ide_ele_min
        if i>=j:
            return res
        i += self.num_max
        j += self.num_max -1
        while(i<=j):
            if(i==j):
                res = self.func(res,self.x[i])
                break
            if(i&1):
                res = self.func(res,self.x[i])
                i += 1
            if(not j&1):
                res = self.func(res,self.x[j])
                j -= 1
            i = i>>1
            j = j>>1
        return res

n = int(readline())
xy = [ list(map(int,i.split()))  for i in readlines()]
mod = 998244353

xy.sort()
ys = [i[1] for i in xy]
ys.sort()
y_rank = {}
for i,y in enumerate(ys):
    y_rank[y] = i


point = [[0,0] for _ in range(n)]
for i,(x,y) in enumerate(xy):
    point[i][0] = i
    point[i][1] = y_rank[y]

seg = Seg_sum([0] * (n+10))

cnt = [[0,0,0,0] for _ in range(n)]
for x,y in point:
    cnt[x][2] = seg.query(0,y)
    cnt[x][1] = seg.query(y,n)
    cnt[x][0] = n-y-1 - cnt[x][1]
    cnt[x][3] = y - cnt[x][2]
    seg.update(y,1)

ex2 = [1] * (n)
for i in range(1,n):
    ex2[i] = (ex2[i-1]*2)%mod

ans = (ex2[n-1] * n) % mod
for n1,n2,n3,n4 in cnt:
    ans += (ex2[n1]-1)*(ex2[n3]-1)*ex2[n2+n4]
    ans %= mod
    ans += (ex2[n2]-1)*(ex2[n4]-1)*ex2[n1+n3]
    ans %= mod
    ans -= (ex2[n1]-1)*(ex2[n2]-1)*(ex2[n3]-1)*(ex2[n4]-1)
    ans %= mod

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
from collections import *

def compress(l):
    l = list(set(l))
    l.sort()
    idx = defaultdict(int)

    for i in range(len(l)):
        idx[l[i]] = i
    
    return idx
    
class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
    
    def add(self, i, x):
        i += 1
        
        while i<=self.n:
            self.bit[i] += x
            i += i&(-i)

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

N = int(input())
xy = [tuple(map(int, input().split())) for _ in range(N)]
xy.sort(key=lambda t: t[0])
idx = compress([xy_i[1] for xy_i in xy])
lbit = BIT(N)
rbit = BIT(N)

for i in range(N):
    rbit.add(i, 1)
    
ans = 0
MOD = 998244353

for i in range(N):
    y = xy[i][1]
    rbit.add(idx[y], -1)
    a = i-lbit.acc(idx[y])
    b = lbit.acc(idx[y])
    c = rbit.acc(idx[y])
    d = N-1-i-rbit.acc(idx[y])
    add = 2*pow(2, N-1, MOD)-1
    pa = pow(2, a, MOD)
    pb = pow(2, b, MOD)
    pc = pow(2, c, MOD)
    pd = pow(2, d, MOD)
    add = (add-(pa-1))%MOD
    add = (add-(pb-1))%MOD
    add = (add-(pc-1))%MOD
    add = (add-(pd-1))%MOD
    add = (add-(pa*pb-pa-pb+1))%MOD
    add = (add-(pb*pc-pb-pc+1))%MOD
    add = (add-(pc*pd-pc-pd+1))%MOD
    add = (add-(pd*pa-pd-pa+1))%MOD
    ans += add
    ans %= MOD
    lbit.add(idx[y], 1)

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
from collections import *

def compress(l):
    l = list(set(l))
    l.sort()
    idx = defaultdict(int)

    for i in range(len(l)):
        idx[l[i]] = i
    
    return idx
    
class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
    
    def add(self, i, x):
        i += 1
        
        while i<=self.n:
            self.bit[i] += x
            i += i&(-i)

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

N = int(input())
xy = [tuple(map(int, input().split())) for _ in range(N)]
xy.sort(key=lambda t: t[0])
idx = compress([xy_i[1] for xy_i in xy])
lbit = BIT(N)
rbit = BIT(N)

for i in range(N):
    rbit.add(i, 1)
    
ans = 0
MOD = 998244353

for i in range(N):
    y = xy[i][1]
    rbit.add(idx[y], -1)
    a = i-lbit.acc(idx[y])
    b = lbit.acc(idx[y])
    c = rbit.acc(idx[y])
    d = N-1-i-rbit.acc(idx[y])
    add = 2*pow(2, N-1, MOD)-1
    add = (add-(pow(2, a, MOD)-1))%MOD
    add = (add-(pow(2, b, MOD)-1))%MOD
    add = (add-(pow(2, c, MOD)-1))%MOD
    add = (add-(pow(2, d, MOD)-1))%MOD
    add = (add-(pow(2, a+b, MOD)-pow(2, a, MOD)-pow(2, b, MOD)+1))%MOD
    add = (add-(pow(2, b+c, MOD)-pow(2, b, MOD)-pow(2, c, MOD)+1))%MOD
    add = (add-(pow(2, c+d, MOD)-pow(2, c, MOD)-pow(2, d, MOD)+1))%MOD
    add = (add-(pow(2, d+a, MOD)-pow(2, d, MOD)-pow(2, a, MOD)+1))%MOD
    ans += add
    ans %= MOD
    lbit.add(idx[y], 1)

print(ans)

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 998244353
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    dat = [LI() for _ in range(N)]
    dat.sort()
    yo = [y for _,y in dat]
    yo.sort()

    up = [0] * N
    dw = [0] * N

    bit = [0] * (N+1)

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

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

    for i in range(N):
        x,y = dat[i]
        y = bisect.bisect_left(yo,y) + 1
        up[i] = bit_sum(y)
        bit_add(y)

    bit = [0] * (N+1)
    for i in range(N-1,-1,-1):
        x,y = dat[i]
        y = bisect.bisect_left(yo,y) + 1
        dw[i] = bit_sum(y)
        bit_add(y)

    ans = N * pow(2,N-1,MOD)
    for i in range(N):
        a = i - up[i]
        b = up[i]
        c = N-(i+1) - dw[i]
        d = dw[i]
        pa = pow(2,a,MOD)
        pb = pow(2,b,MOD)
        pc = pow(2,c,MOD)
        pd = pow(2,d,MOD)
        pad = pow(2,a+d,MOD)
        pbc = pow(2,b+c,MOD)
        p = (pad-1) - (pa-1) - (pd-1)
        q = (pbc-1) - (pb-1) - (pc-1)
        x = p * pbc
        y = q * pad
        z = p * q
        ans = (ans + x + y - z) % MOD
    print(ans)

if __name__ == '__main__':
    main()