I recommend you to reinstall all packages on your system that are known to have files in the deleted /usr/lib/gcc directory.
The output of dpkg -S /usr/lib/gcc told us which packages this are, in your case:
gcc-5-base:amd64, libgcc-5-dev:amd64, cpp-5, gcc-5, gcc-6-base:amd64
Now let's reinstall all of them:
sudo apt-get install --reinstall gcc-5-base:amd64 libgcc-5-dev:amd64 cpp-5 gcc-5 gcc-6-base:amd64
You can alternatively automate this process and leave the parsing of the package list to sed.
That way you only have to run this single command:
sudo apt-get install --reinstall $(dpkg -S /usr/lib/gcc | sed 's/,\|: .*//g')